洪水填充算法

2023-06-21 06:42:03 62

给出一个矩阵；矩阵代表一个屏幕。屏幕的每个元素(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

洪水填充算法

输入和输出

算法

示例

热门推荐

随机推荐