洪水填充算法（floodfill）
洪水填充算法（floodfill）是一种图像处理算法，它用于对连通的区域进行染色。该算法的基本思想是从指定的起始点开始，以该点的颜色为基准，向该点的四周（上、下、左、右）进行填充，直到找到所有相邻的点，并将这些点染成指定的颜色。这个过程类似于洪水从起始点开始向四周蔓延，最终填满整个区域。
下面是一个简单的实现洪水填充算法的C++代码示例，我们以一个二维数组来表示需要填充的图像：
#include <iostream>
using namespace std;
// 定义图像的行列数
const int ROWS = 10;
const int COLS = 10;
// 定义一个二维数组表示图像
int image[ROWS][COLS] = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
};
// 定义一个辅助函数，用于打印图像
void printImage()
{
for(int i = 0; i < ROWS; i++)
{
for(int j = 0; j < COLS; j++)
{
cout << image[i][j] << " ";
}
cout << endl;
}
}
// 定义洪水填充函数
void floodFill(int x, int y, int oldColor, int newColor)
{
// 如果当前位置的颜色已经被改变，直接返回
if(image[x][y] != oldColor)
{
return;
}
// 否则，将当前位置的颜色改为新颜色
image[x][y] = newColor;
// 递归填充当前位置的四周
if(x > 0)
{
floodFill(x-1, y, oldColor, newColor); // 上方
}
if(x < ROWS - 1)
{
floodFill(x+1, y, oldColor, newColor); // 下方
}
if(y > 0)
{
floodFill(x, y-1, oldColor, newColor); // 左侧
}
if(y < COLS - 1)
{
floodFill(x, y+1, oldColor, newColor); // 右侧
}
}
int main()
{
cout << "原始图像：" << endl;
printImage();
// 将(1,1)处的颜色改为2
floodFill(1, 1, 0, 2);
cout << "填充后的图像：" << endl;
printImage();
return 0;
}在上面的代码中，我们首先定义了一个10行10列的二维数组`image`，表示需要填充的图像。在`printImage`函数中，我们简单地遍历二维数组，并将每个元素打印出来。
在`floodFill`函数中，我们首先判断当前位置的颜色是否与旧颜色相同，如果不同则直接返回。否则，将当前位置的颜色改为新颜色，并递归地填充当前位置的四周。
在`main`函数中，我们首先打印出原始图像，然后调用`floodFill`函数，将(1,1)处的颜色改为2。最后，我们再次打印出填充后的图像。
接下来，我们用一个示意图来演示洪水填充算法的执行过程。
原始图像：
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
在示意图中，我们用白色方格表示颜色为0的位置，用灰色方格表示颜色为1的位置，用红色方格表示当前正在填充的位置，用蓝色方格表示已经填充过的位置。
首先，我们从(1,1)处开始填充。由于该位置的颜色为0，与旧颜色0相同，因此将该位置的颜色改为2，并递归地填充周围的位置。
接下来，我们从(0,1)处开始填充。由于该位置的颜色为1，与旧颜色0不同，因此不进行填充。
然后，我们从(2,1)处开始填充。由于该位置的颜色为1，与旧颜色0不同，因此不进行填充。
接着，我们从(1,0)处开始填充。由于该位置的颜色为1，与旧颜色0不同，因此不进行填充。
然后，我们从(1,2)处开始填充。由于该位置的颜色为1，与旧颜色0不同，因此不进行填充。
接下来，我们从(0,2)处开始填充。由于该位置的颜色为1，与旧颜色0不同，因此不进行填充。
然后，我们从(2,2)处开始填充。由于该位置的颜色为1，与旧颜色0不同，因此不进行填充。
接着，我们从(0,0)处开始填充。由于该位置的颜色为1，与旧颜色0不同，因此不进行填充。
然后，我们从(2,0)处开始填充。由于该位置的颜色为1，与旧颜色0不同，因此不进行填充。
最后，我们从(1,3)处开始填充。由于该位置的颜色为1，与旧颜色0不同，因此不进行填充。
填充结束后，我们得到了如下的图像：
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
接下来，我们用C++代码来实现洪水填充算法。假设我们的图像是一个二维数组，用0表示空白，1表示障碍，2表示已填充的区域。以下是示例代码：
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 10; // 图像的大小
int image[MAXN][MAXN] = { // 图像，0表示空白，1表示障碍，2表示已填充
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
// 定义二维向量，用于表示图像中的位置
struct Point {
int x, y;
Point(int x=0, int y=0): x(x), y(y) {}
};
// 定义一个用于比较二维向量的函数，用于STL的排序
bool operator<(const Point& a, const Point& b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
// 定义一个函数，用于输出图像
void printImage() {
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
cout << image[i][j] << " ";
}
cout << endl;
}
}
// 定义一个函数，用于执行洪水填充
void floodFill(int x, int y) {
queue<Point> q; // 用于BFS遍历的队列
q.push(Point(x, y)); // 将起点加入队列
image[x][y] = 2; // 将起点标记为已填充
while (!q.empty()) {
Point p = q.front();
q.pop();
// 对于p的四个相邻位置，如果颜色相同且未被访问过，则将其加入队列并标记为已填充
if (p.x-1 >= 0 && image[p.x-1][p.y] == 0) {
q.push(Point(p.x-1, p.y));
image[p.x-1][p.y] = 2;
}
if (p.x+1 < MAXN && image[p.x+1][p.y] == 0) {
q.push(Point(p.x+1,p.y));
image[p.x+1][p.y] = 2;
}
if (p.y-1 >= 0 && image[p.x][p.y-1] == 0) {
q.push(Point(p.x, p.y-1));
image[p.x][p.y-1] = 2;
}
if (p.y+1 < MAXN && image[p.x][p.y+1] == 0) {
q.push(Point(p.x, p.y+1));
image[p.x][p.y+1] = 2;
}
}
}
// 主函数
int main() {
cout << "原图像：" << endl;
printImage();
cout << endl << "执行洪水填充算法：" << endl;
floodFill(2, 2);
cout << endl << "填充后的图像：" << endl;
printImage();
return 0;
}输出结果如下：
原图像： 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 执行洪水填充算法： 填充后的图像： 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 2 2 2 0 0 1 1 0 0 2 0 0 2 0 0 1 1 0 0 2 0 0 2 0 0 1 1 0 0 2 2 2 2 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
可以看到，我们成功地填充了从(2,2)开始的区域，并将其标记为2。
我们也可以通过一些示意图来更直观地展示洪水填充算法的执行过程。假设我们要将从(2,2)开始的区域填充为2，我们可以绘制如下的示意图：
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 X 0 0 X 0 0 1 1 0 0 X 0 0 X 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
其中X表示当前正在考虑的像素点，蓝色箭头表示当前像素点将要扩展的像素点，黄色填充表示已经被标记为2的像素点。下面是对应的执行过程：
开始执行洪水填充算法，将起点(2,2)加入队列。
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 X 0 0 X 0 0 1 1 0 0 X 0 0 X 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
取出队头元素(2,2)，将其标记为2，并将其相邻的未标记像素点(3,2)和(2,3)加入队列。
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 0 0 0 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 X 0 0 X 0 0 1 1 0 0 X 0 0 X 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
取出队头元素(3,2)，将其标记为2，并将其相邻的未标记像素点(4,2)和(3,3)加入队列。
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 0 0 0 0 0 1 1 0 0 2 X X X 0 0 1 1 0 0 X 0 0 X 0 0 1 1 0 0 X 0 0 X 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
取出队头元素(2,3)，将其标记为2，并将其相邻的未标记像素点(2,4)和(3,3)加入队列。
Copy code1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 2 0 0 0 0 1 1 0 0 2 X X X 0 0 1 1 0 0 X 0 0 X 0 0 1 1 0 0 X 0 0 X 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
取出队头元素(4,2)，将其标记为2，并将其相邻的未标记像素点(5,2)和(4,3)加入队列。
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 2 0 0 0 0 1 1 0 0 2 X X X 0 0 1 1 0 0 2 0 0 X 0 0 1 1 0 0 X 0 0 X 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1
取出队头元素(3,3)，将其标记为2，并将其相邻的未标记像素点(2,3)、(4,3)和(3,4)加入队列。
Copy code1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 2 0 0 0 0 1 1 0 0 2 X X X 0 0 1 1 0 0 2 0 0 X 0 0 1 1 0 0 2 0 0 X 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
取出队头元素(2,4)，将其标记为2，并将其相邻的未标记像素点(2,5)和(3,4)加入队列。
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 2 2 0 0 0 1 1 0 0 2 X X X 0 0 1 1 0 0 2 0 0 X 0 0 1 1 0 0 2 0 0 X 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
取出队头元素(4,3)，将其标记为2，并将其相邻的未标记像素点(3,3)和(4,4)加入队列。
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 2 2 0 0 0 1 1 0 0 2 X X X 0 0 1 1 0 0 2 2 0 X 0 0 1 1 0 0 2 0 0 X 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
取出队头元素(2,5)，将其标记为2，并将其相邻的未标记像素点(1,5)和(2,6)加入队列。
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 2 2 0 0 0 1 1 0 0 2 X X X 0 0 1 1 0 0 2 2 2 X 0 0 1 1 0 0 2 0 0 X 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
取出队头元素(3,4)，将其标记为2，并将其相邻的未标记像素点(2,4)和(4,4)加入队列
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 2 2 0 0 0 1 1 0 0 2 X X X 0 0 1 1 0 0 2 2 2 X 0 0 1 1 0 0 2 0 0 X 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
取出队头元素(4,4)，将其标记为2，并将其相邻的未标记像素点(3,4)和(4,3)加入队列。
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 2 2 0 0 0 1 1 0 0 2 X X X 0 0 1 1 0 0 2 2 2 2 0 0 1 1 0 0 2 0 0 2 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
取出队头元素(4,3)，将其标记为2，并将其相邻的未标记像素点(4,2)加入队列。
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 2 2 0 0 0 1 1 0 0 2 X X X 0 0 1 1 0 0 2 2 2 2 0 0 1 1 0 0 2 0 0 2 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
取出队头元素(4,2)，将其标记为2，并将其相邻的未标记像素点(4,1)加入队列。
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 2 2 0 0 0 1 1 0 0 2 X X X 0 0 1 1 0 0 2 2 2 2 0 0 1 1 0 0 2 0 0 2 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
取出队头元素(4,1)，将其标记为2。
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 2 2 2 0 0 0 1 1 0 0 2 X X X 0 0 1 1 0 0 2 2 2 2 0 0 1 1 0 0 2 0 0 2 0 0 1 1 0 0 X X X X 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
队列为空，算法结束。
最终的填充结果如下：
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 1 2 2 2 X X X 2 2 1 1 2 2 2 2 2 2 2 2 1 1 2 2 2 0 0 2 2 2 1 1 2 2 X X X X 2 2 1 1 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
在代码中，我们使用了一个辅助数组visited来记录像素点是否已经被标记，将已经标记的像素点置为true，否则置为false。当我们取出队头元素时，需要先检查它是否越界，以及是否已经被标记。如果没有越界且没有被标记，则将其标记为2，并将其相邻的未标记像素点加入队列。这个过程一直持续到队列为空，算法结束。
- 上一篇：图的宽度优先遍历算法
- 下一篇：算法中的动态规划的基本思路