CC++ & Algorithm

Flood Fill泛洪算法：像水漫金山一样填充颜色

困难4
语言版本：C++
概述：从指定位置开始，把连通区域内相同颜色的格子全部替换成新颜色，常用于画图软件的油漆桶工具。

? Flood Fill 泛洪算法：像水漫金山一样填充颜色

你有没有在画图软件里用过“油漆桶”工具？点一下封闭区域的内部，整个区域就被染上新的颜色，像水一样自动扩散，直到碰到边界才停下。这个神奇的功能背后，就是 Flood Fill（泛洪算法）。

泛洪算法的核心是：从一个种子点出发，把与它相连（上下左右相邻）且颜色相同的所有格子，全部替换成新颜色。它就像水漫金山——水从源头流出去，漫过所有能到达的地方，直到被墙挡住。

这个算法不仅用于画图，还能解决许多实际问题：

  • 计算一张图片里有多少个独立的彩色区域（比如统计照片中的云朵数量）；
  • 在迷宫中标记出从起点能走到的所有位置；
  • 在电子地图上点击一个湖泊，让它全部变成蓝色。

下面我们就一步步拆解这个算法，看看它到底怎么工作。

? 什么是连通？四连通 vs 八连通

泛洪算法中的“相连”通常有两种定义：

? 四连通

只考虑 上、下、左、右 四个方向（像十字架）。
比如你点了一个格子，只有上下左右四个紧邻的格子算“邻居”。

   ↑
← 格 →
   ↓

? 八连通

除了上下左右，还考虑 左上、右上、左下、右下 四个对角方向（像九宫格的全部八个邻居）。

↖ ↑ ↗
← 格 →
↙ ↓ ↘

用哪种连通方式，取决于题目要求。最常见的默认是四连通，但画图软件里通常用的是八连通（因为对角触摸也算相连）。

生活中的例子：假如你在一张方格纸上用笔涂满一个区域，四连通就像只能横向或纵向爬的蚂蚁，而八连通像可以斜着走的蜘蛛。

? DFS 实现：递归扩散就像波纹

最早的代码就是用的 DFS（深度优先搜索）。它的思路很简单：

  1. 从种子点出发；
  2. 如果当前格子合法（在边界内、颜色是目标色），就把它染成新颜色；
  3. 然后递归地处理上、下、左、右四个邻居；
  4. 遇到边界或颜色不对就回头。

你可以想象成在水面上投下一颗石子，涟漪一圈一圈向外扩散，但实际上DFS是沿着一条路走到底，再回来走另一条路。

代码注释版（在原代码基础上补充了中文注释）

#include <iostream>
#include <vector>
using namespace std;

const int R = 5, C = 5;   // 网格行数、列数
int grid[R][C] = {         // 初始网格：0表示白色，1表示黑色
    {0, 0, 1, 1, 1},
    {0, 0, 0, 1, 0},
    {1, 0, 0, 1, 0},
    {1, 1, 0, 0, 0},
    {0, 0, 0, 1, 0}
};
int newColor = 2;          // 新颜色（绿色）
int targetColor = 0;       // 要替换的旧颜色（白色）

// 深度优先搜索填充函数
void floodFillDFS(int x, int y) {
    // 1. 越界检查
    if (x < 0 || x >= R || y < 0 || y >= C) return;
    // 2. 不是目标颜色 或 已经被填充过（等于newColor）则返回
    if (grid[x][y] != targetColor) return;

    grid[x][y] = newColor;  // 染色

    // 3. 递归向四个方向扩散
    floodFillDFS(x - 1, y);     // 上
    floodFillDFS(x + 1, y);     // 下
    floodFillDFS(x, y - 1);     // 左
    floodFillDFS(x, y + 1);     // 右
}

void printGrid() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    cout << "填充前:" << endl;
    printGrid();

    int startX = 1, startY = 1;          // 从第2行第2列开始（下标从0起）
    targetColor = grid[startX][startY];  // 获取起始点的颜色（这里是白色0）
    if (targetColor != newColor) {       // 防止新旧颜色相同导致无限递归
        floodFillDFS(startX, startY);
    }

    cout << "填充后:" << endl;
    printGrid();
    return 0;
}

输出结果：
填充前：
0 0 1 1 1
0 0 0 1 0
1 0 0 1 0
1 1 0 0 0
0 0 0 1 0
填充后：
2 2 1 1 1
2 2 2 1 0
1 2 2 1 0
1 1 2 2 2
2 2 2 1 0

可以看到，所有与(1,1)连通的白色（0）都被染成了绿色（2），而右上角被黑色（1）隔开的白色没有被填充。

? BFS 实现：队列扩散像洪水推进

DFS 递归虽然写起来简单，但有一个大缺点：当网格很大时，递归深度可能达到几万层，导致栈溢出。这时候可以用 BFS（广度优先搜索） 来避免。

BFS 的思路是用一个队列，先把起点放进去，然后不断取出队首，染色，再把它的四个邻居中符合条件的都入队。这样一层一层向外扩散，就像洪水从源头同时向四周漫开。

BFS 版代码（每行变量都加了中文注释）

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int R = 5, C = 5;
int grid[R][C] = {
    {0, 0, 1, 1, 1},
    {0, 0, 0, 1, 0},
    {1, 0, 0, 1, 0},
    {1, 1, 0, 0, 0},
    {0, 0, 0, 1, 0}
};
int newColor = 2;          // 新颜色
int targetColor = 0;       // 旧颜色

// 方向数组：上下左右对应的偏移 (dx[i], dy[i])
int dx[4] = {-1, 1, 0, 0}; // 行方向：上(-1), 下(+1), 左(0), 右(0)
int dy[4] = {0, 0, -1, 1}; // 列方向：上(0), 下(0), 左(-1), 右(+1)

void floodFillBFS(int startX, int startY) {
    if (grid[startX][startY] != targetColor) return; // 如果起点颜色不对，直接退出

    queue<pair<int, int>> q;   // 存储待处理格子坐标的队列
    q.push({startX, startY});  // 将起点入队
    grid[startX][startY] = newColor;  // 染色（防止重复入队）

    while (!q.empty()) {
        int x = q.front().first;   // 当前格子的行号
        int y = q.front().second;  // 当前格子的列号
        q.pop();

        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];   // 邻居的行号
            int ny = y + dy[i];   // 邻居的列号

            // 检查边界和颜色
            if (nx >= 0 && nx < R && ny >= 0 && ny < C && grid[nx][ny] == targetColor) {
                grid[nx][ny] = newColor;  // 染色
                q.push({nx, ny});         // 入队，待继续扩散
            }
        }
    }
}

void printGrid() { /* 同前，省略 */ }

int main() {
    cout << "填充前:" << endl;
    printGrid();

    int startX = 1, startY = 1;
    targetColor = grid[startX][startY];
    if (targetColor != newColor) {
        floodFillBFS(startX, startY);
    }

    cout << "填充后:" << endl;
    printGrid();
    return 0;
}

DFS vs BFS 的选择：

  • DFS 代码更短，适合小规模（<1000 个格子）或深度不深的情况。
  • BFS 不会栈溢出，在大图上更安全，而且能自然求出最短路径（如果搭配距离记录）。

⚠️ 新手最容易犯的 4 个错误

  1. 没有检查新颜色是否等于旧颜色
    假如 targetColor 和 newColor 都是 2，那么 DFS 会一直染色，但染色后还是等于 targetColor，导致死循环（无限递归）。
    ✅ 处理：在调用前判断 if (targetColor != newColor) 或者函数里第一次染色后立即返回。

  2. 忘记在 BFS 中染色后再入队
    如果只入队而不染色，别人队可能会再次把同一个格子入队很多次，导致无限循环或超时。
    ✅ 处理：每次入队前先染色（grid[nx][ny] = newColor），确保每个格子只入队一次。

  3. 只检查是否等于旧颜色，没检查是否越界
    如果不先检查越界，数组下标可能变成负数或超过大小，程序崩溃。
    ✅ 处理：总是先检查越界，再检查颜色。

  4. 忽略连通方式的变化
    题目可能要求八连通（包括对角），但默认只写了四个方向。
    ✅ 处理：仔细读题，如果是八连通，就要用 8 个方向数组。

? 完整示例：统计岛屿数量（Flood Fill 的经典应用）

假设有一个地图，1 表示陆地，0 表示海水。我们要找出有多少个孤立的岛屿（每个岛屿是一块四连通的 1）。

#include <iostream>
#include <vector>
using namespace std;

// 方向数组（四连通）
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void dfs(vector<vector<int>>& grid, int x, int y) {
    int R = grid.size(), C = grid[0].size();
    if (x < 0 || x >= R || y < 0 || y >= C || grid[x][y] != 1) return;
    grid[x][y] = 0;  // 标记为已访问（相当于“沉没”）
    for (int i = 0; i < 4; i++) {
        dfs(grid, x + dx[i], y + dy[i]);
    }
}

int numIslands(vector<vector<int>>& grid) {
    int count = 0;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == 1) {   // 发现一个新陆地
                dfs(grid, i, j);     // 把它所在的整个岛屿染成“水”
                count++;             // 岛屿数量加1
            }
        }
    }
    return count;
}

int main() {
    vector<vector<int>> map = {
        {1, 1, 0, 0, 0},
        {1, 1, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 0, 0, 1, 1}
    };
    cout << "岛屿数量: " << numIslands(map) << endl;  // 输出 3
    return 0;
}

这个例子中，每找到一个 1，就用 Flood Fill 把整个连通块都变成 0，然后继续找下一个。这就是用泛洪算法统计连通块数量的标准套路。

? 相关知识点指引

  • 图的遍历：Flood Fill 本质上是图的遍历，DFS 和 BFS 是两种基本方法。
  • 连通分量：在无向图中找连通块，Flood Fill 是常用的手法。
  • 迷宫最短路径：BFS 版本稍加修改（记录步数）就能求出从起点到终点的最短路径长度。
  • 图像处理中的区域填充：除了四连通/八连通，还有基于种子点的扫描线填充等优化算法。
  • 堆栈溢出与递归深度：如果 DFS 递归太深，可以改为显式栈（用栈模拟递归），或者直接用 BFS。

掌握了 Flood Fill，你就掌握了“扩散”类问题的核心思想。下次看到类似“填充”“连通区域”“岛屿数量”的题目，就可以自信地说：我用泛洪算法搞定它！

例题精讲

1单选题

在实现Flood Fill算法时，如果使用深度优先搜索（DFS）的递归方式，对于一张500x500的网格，最坏情况下可能会遇到什么问题？

A内存泄漏
B栈溢出
C死循环
D数组越界
2判断题

Flood Fill算法中，如果采用广度优先搜索（BFS）并借助队列实现，可以避免递归导致的栈溢出问题。

3填空题
给定函数 void floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) ，其中image是二维整数网格，每个格子颜色为整数。要求将(sr,sc)所在连通区域（四连通）中所有与image[sr][sc]相同颜色的格子替换为newColor。请补全以下DFS递归实现：

void floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    int oldColor = image[sr][sc];
    if (oldColor == newColor) return;
    int m = image.size(), n = image[0].size();
    if (sr < 0 || sr >= m || sc < 0 || sc >= n) return;
    if (image[sr][sc] != oldColor) return;
    image[sr][sc] = newColor;
    floodFill(image, sr+1, sc, newColor);
    floodFill(image, sr-1, sc, newColor);
    floodFill(image, sr, sc+1, newColor);
    ___;
}
4单选题

在使用Flood Fill算法进行图像填充时，如果不小心将起始颜色和新的颜色设置为相同的值，会发生什么？

A导致死循环
B导致栈溢出
C填充无限区域
D什么都不做，正常结束
5判断题

Flood Fill算法只能应用于矩形网格，不能应用于不规则区域。