洪水填充算法
给出一个矩阵;矩阵代表一个屏幕。屏幕的每个元素(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#define M 8 #define N 8 using namespace std; int screen[M][N] = { //屏幕尺寸和颜色 {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) { //用新颜色替换(x,y)的先前颜色 if (x < 0 || x >= M || y < 0 || y >= N) //当点超过屏幕时 return; if (screen[x][y] != prevColor) //如果point(x,y)不包含prevColor,则什么都不做 return; screen[x][y] = newColor; //更新颜色 fillScreen(x+1, y, prevColor, newColor); //对于(x,y)的右边 fillScreen(x-1, y, prevColor, newColor); //对于(x,y)的左边 fillScreen(x, y+1, prevColor, newColor); //对于(x,y)的顶部 fillScreen(x, y-1, prevColor, newColor); //对于(x,y)的底部 } void floodFill(int x, int y, int newColor) { int prevColor = screen[x][y]; //在更换新颜色之前先取颜色 fillScreen(x, y, prevColor, newColor); } int main() { int x = 4, y = 4, newColor = 3; cout << "上一画面: "<< endl; for (int i=0; i 输出结果 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 更新画面: 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