洪水填充算法

  • Z时代
  • 2024-01-10
  • 分类：综合

给出一个矩阵；矩阵代表一个屏幕。屏幕的每个元素 (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] = {    //屏幕尺寸和颜色
   {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<M; i++) {
      for (int j=0; j<N; j++)
         cout << screen[i][j] << " ";
      cout << endl;
   }
   cout << endl;
   floodFill(x, y, newColor);    //从 (4, 4) 开始，使用新颜色 3
   
   cout << "更新画面： "<< 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
更新画面：
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

以上是 洪水填充算法 的全部内容， 来源链接： utcz.com/z/359584.html

回到顶部