Flood 填充算法 – 如何在 C++ 中实现 paint 中的 fill()
c++server side programmingprogramming更新于 2025/5/31 12:22:17
在这个问题中，我们给出了一个表示二维屏幕的二维数组、屏幕上要填充颜色的像素的坐标和颜色。我们的任务是创建一个程序来为当前像素和所有具有该颜色的相邻像素着色。
在 paint 中着色，我们将选择一种颜色并用画笔单击给定的像素。
让我们举一个例子来理解这个问题
Input: Sceen[][] =
{{W, W, B, W, W, W, W, W},
{W, W, W, W, W, W, B, B},
{W, B, B, W, W, B, W, W},
{W, Y, Y, Y, Y, B, W, B},
{B, W, W, Y, Y, B, W, B},
{B, W, W, Y, Y, Y, Y, B},
{W, B, W, W, W, Y, W, W},
{W, W, B, B, W, Y, Y, W}};
X = 5, Y = 5, newColor = R.
Output:
{{W, W, B, W, W, W, W, W},
{W, W, W, W, W, W, B, B},
{W, B, B, W, W, B, W, W},
{W, R, R, R, R, B, W, B},
{B, W, W, R, R, B, W, B},
{B, W, W, R, R, R, R, B},
{W, B, W, W, W, R, W, W},
{W, W, B, B, W, R, R, W}};
洪水填充算法
在此算法中，当像素已经处于所选的先前颜色时，将用新颜色填充像素。如果先前的颜色不是先前的颜色，则不会填充该像素。填充像素后，它将检查其上、下、左和右像素以执行相同操作。在此处了解更多信息。
解决方法
解决问题的一种方法是使用递归方法。我们将找到需要着色的第一个尖晶石，然后检查其所有 4 个相邻像素。适合相同颜色，然后用新颜色替换它，并对当前像素的邻居重复此操作。如果相邻像素的颜色不同，则保留它。按照以下步骤操作，直到所有与起始像素颜色相同的相邻尖晶石都被着色。然后停止填充算法。
示例
程序说明我们的解决方案的工作原理
#include<iostream>
using namespace std;
#define M 8
#define N 8
void fillColorAdj(char screen[][N], int x, int y, char oldColor, char color){
if (x < 0 || x >= M || y < 0 || y >= N)
return;
if (screen[x][y] != oldColor)
return;
if (screen[x][y] == color)
return;
screen[x][y] = color;
fillColorAdj(screen, x+1, y, oldColor, color);
fillColorAdj(screen, x-1, y, oldColor, color);
fillColorAdj(screen, x, y+1, oldColor, color);
fillColorAdj(screen, x, y-1, oldColor, color);
}
void fillColor(char screen[][N], int x, int y, char color){
char oldColor = screen[x][y];
if(oldColor==color) return;
fillColorAdj(screen, x, y, oldColor, color);
}
int main(){
char screen[M][N] = {{'W', 'W', 'B', 'W', 'W', 'W', 'W', 'W'},
{'W', 'W', 'W', 'W', 'W', 'W', 'B', 'B'},
{'W', 'B', 'B', 'W', 'W', 'B', 'W', 'W'},
{'W', 'Y', 'Y', 'Y', 'Y', 'B', 'W', 'B'},
{'B', 'W', 'W', 'Y', 'Y', 'B', 'W', 'B'},
{'B', 'W', 'W', 'Y', 'Y', 'Y', 'Y', 'B'},
{'W', 'B', 'W', 'W', 'W', 'Y', 'W', 'W'},
{'W', 'W', 'B', 'B', 'W', 'Y', 'Y', 'W'},};
int x = 5, y = 5;
char color = 'R';
cout<<"The initial screen cordinates are : \n";
for (int i=0; i<M; i++){
for (int j=0; j<N; j++)
cout<<screen[i][j]<<"\t";
cout<<endl;
}
fillColor(screen, x, y, color);
cout<<"\nThe screen cordinates after coloring are : \n";
for (int i=0; i<M; i++){
for (int j=0; j<N; j++)
cout<<screen[i][j]<<"\t";
cout<<endl;
}
}
输出
The initial screen cordinates are : W W B W W W W W W W W W W W B B W B B W W B W W W Y Y Y Y B W B B W W Y Y B W B B W W Y Y Y Y B W B W W W Y W W W W B B W Y Y W The screen cordinates after coloring are : W W B W W W W W W W W W W W B B W B B W W B W W W R R R R B W B B W W R R B W B B W W R R R R B W B W W W R W W W W B B W R R W
