洪水填充算法原理
洪水填充算法（Flood Fill Algorithm）是一种经典的图像处理算法，常用于填充封闭区域，例如在绘图程序中填充多边形的内部区域。这种算法的基本思想是从一个起始点出发，将其相邻的像素填充为相同的颜色，然后继续对这些相邻像素的相邻像素进行同样的操作，直到整个封闭区域都被填充。
原理概述
起始点：选择一个像素作为填充的起始点（通常是用户点击的地方）。
检查邻点：检查该像素的四个（或八个）相邻像素，判断是否满足填充条件（例如颜色与起始点的颜色相同）。
填充：将满足条件的像素颜色替换为目标颜色。
递归或迭代：对所有满足条件的相邻像素重复上述过程，直到所有应填充的区域都被处理。
算法实现
洪水填充算法有两种常见的实现方式：
递归实现：
从起始像素开始，递归地调用自身处理其相邻像素。
由于递归深度可能较大，容易导致栈溢出，因此不适用于非常大的图像或复杂的区域。
迭代实现（使用堆栈或队列）：
通过使用堆栈（深度优先）或队列（广度优先），避免了递归的栈深度问题。
迭代版本更适合处理大型图像或复杂的填充区域。
步骤示例
假设在一个二维像素数组中填充颜色：
将起始点入栈或入队。
当栈或队列非空时，弹出一个像素。
如果该像素颜色与目标颜色相同，将其颜色更新为新的颜色。
将该像素的相邻像素（上、下、左、右，或包括对角线）依次入栈或入队。
重复上述过程，直到栈或队列为空。
应用
图像编辑器：用于填充封闭区域的颜色。
路径查找：在迷宫或地图中查找从一个起始点扩展到所有可达位置的路径。
区域分割：在图像处理中，分割不同颜色或特征的区域。
洪水填充算法简单且有效，在许多应用场景中都得到了广泛使用。
下面是一个简单的C++实现洪水填充算法的代码示例。这个实现使用迭代方法（队列）来避免递归导致的栈溢出问题。
C++代码实现
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void floodFill(vector<vector<int>>& image, int x, int y, int newColor) {
int oldColor = image[x][y];
if (oldColor == newColor) return;
int rows = image.size();
int cols = image[0].size();
queue<pair<int, int>> q;
q.push({x, y});
// 方向数组，表示上下左右四个方向
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while (!q.empty()) {
auto [cx, cy] = q.front();
q.pop();
image[cx][cy] = newColor;
// 检查四个方向的相邻像素
for (auto& dir : directions) {
int nx = cx + dir[0];
int ny = cy + dir[1];
// 检查是否在边界内并且颜色与旧颜色相同
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && image[nx][ny] == oldColor) {
q.push({nx, ny});
}
}
}
}
void printImage(const vector<vector<int>>& image) {
for (const auto& row : image) {
for (const auto& pixel : row) {
cout << pixel << " ";
}
cout << endl;
}
}
int main() {
vector<vector<int>> image = {
{1, 1, 1, 2, 2},
{1, 1, 0, 2, 2},
{1, 0, 0, 2, 2},
{1, 1, 1, 0, 0},
{1, 1, 1, 2, 2},
};
int startX = 1;
int startY = 1;
int newColor = 3;
cout << "Original image:" << endl;
printImage(image);
floodFill(image, startX, startY, newColor);
cout << "\nImage after flood fill:" << endl;
printImage(image);
return 0;
}代码解释
函数
floodFill：参数
image：二维图像数组。参数
x, y：起始像素的坐标。参数
newColor：要填充的目标颜色。首先检查起始像素的颜色是否与目标颜色相同，如果相同则不进行任何操作。
使用队列进行广度优先搜索（BFS），从起始像素开始，逐步将相邻的同颜色像素替换为新颜色。
方向数组
directions：用于表示移动的四个方向（上、下、左、右），通过加减坐标来确定相邻像素的位置。
主函数
main：初始化一个二维图像，指定起始点和新颜色，然后调用
floodFill函数进行填充。填充前后打印图像，方便观察结果。
输出示例
程序执行后，将输出填充前和填充后的图像，展示洪水填充的效果。
