数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时装研究
法律研究泛洪填充算法
给定一个矩阵，该矩阵表示一个屏幕。屏幕的每个元素 (i, j) 被表示为一个像素，该像素的颜色用不同的数字标记。在此算法中，当像素已有选择的先前的颜色时，该像素将填充新的颜色。如果先前的颜色并不是先前的颜色，则将不会填充该像素。在填充一个像素之后，它将检查其上、下、左、右像素以执行相同的操作。
这个想法真的很简单，首先，我们检查选定的位置是否被先前的颜色填充，如果未被填充，算法将不起作用。否则，它将用新颜色填充该像素，并对其四个相邻像素进行递归。
输入和输出
Input: The screen matrix: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 2 2 2 2 0 1 0 1 1 1 2 2 0 1 0 1 1 1 2 2 2 2 0 1 1 1 1 1 2 1 1 1 1 1 1 1 2 2 1 Output: Screen matrix after flood fill 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 3 3 3 3 0 1 0 1 1 1 3 3 0 1 0 1 1 1 3 3 3 3 0 1 1 1 1 1 3 1 1 1 1 1 1 1 3 3 1
算法
fillScreen(x, y, prevColor, newColor)
输入：要开始的 (x,y) 坐标、先前的颜色和新颜色。
输出 −在可能的情况下，在将颜色从先前的颜色更改为新的颜色后，显示屏幕。
Begin if (x, y) not in the screen range, then return if color of (x, y) ≠ prevColor, then return screen[x, y] := newColor fillScreen(x+1, y, prevColor, newColor) fillScreen(x-1, y, prevColor, newColor) fillScreen(x, y+1, prevColor, newColor) fillScreen(x, y-1, prevColor, newColor) End
示例
#include<iostream>
#define M 8
#define N 8
using namespace std;
int screen[M][N] = { //the screen dimention and colors
{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 2, 2, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 2, 2, 0},
{1, 1, 1, 1, 1, 2, 1, 1},
{1, 1, 1, 1, 1, 2, 2, 1}
};
void fillScreen(int x, int y, int prevColor, int newColor) { //replace previous color of (x,y), with new color
if (x < 0 || x >= M || y < 0 || y >= N) //when point exceeds the screen
return;
if (screen[x][y] != prevColor) //if the point(x,y) are not containing prevColor, do nothing
return;
screen[x][y] = newColor; //update the color
fillScreen(x+1, y, prevColor, newColor); //for the right of (x,y)
fillScreen(x-1, y, prevColor, newColor); //for the left of (x,y)
fillScreen(x, y+1, prevColor, newColor); //for the top of (x,y)
fillScreen(x, y-1, prevColor, newColor); //for the bottom of (x,y)
}
void floodFill(int x, int y, int newColor) {
int prevColor = screen[x][y]; //take the color before replacing with new color
fillScreen(x, y, prevColor, newColor);
}
int main() {
int x = 4, y = 4, newColor = 3;
cout << "Previous screen: "<< endl;
for (int i=0; i<M; i++) {
for (int j=0; j<N; j++)
cout << screen[i][j] << " ";
cout << endl;
}
cout << endl;
floodFill(x, y, newColor); //start from (4, 4), with new color 3
cout << "Updated screen: "<< endl;
for (int i=0; i<M; i++) {
for (int j=0; j<N; j++)
cout << screen[i][j] << " ";
cout << endl;
}
}输出
Previous screen 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 2 2 2 2 0 1 0 1 1 1 2 2 0 1 0 1 1 1 2 2 2 2 0 1 1 1 1 1 2 1 1 1 1 1 1 1 2 2 1 Updated screen: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 3 3 3 3 0 1 0 1 1 1 3 3 0 1 0 1 1 1 3 3 3 3 0 1 1 1 1 1 3 1 1 1 1 1 1 1 3 3 1
更新于： 17-6 月-2020
1 千次浏览
广告