C++Flood Fill算法

像倒油漆一样填色——C++ Flood Fill 算法

在画图软件里，你用过“油漆桶”工具吗？点一下某个区域，整个相连的相同颜色区域都会被填成新颜色。Flood Fill 算法做的就是这件事：从一个起点格子出发，把和它“连通”且颜色相同的所有格子都改成新颜色。这里的“连通”通常指上下左右四个方向（也可以包括对角线），就像水在平面上向四周漫开。

Flood Fill 是图的遍历的一种应用——把二维网格看作一张图，每个格子是一个节点，上下左右相邻的格子之间有边。它常用来解决“连通区域填充”问题，比如图像填充、扫雷游戏里点击空白格子后展开一片区域、地图中标记国家或省份等。

生活中的类比：用墨水染湿一张纸

想象你有一张白纸，上面画了一些黑色线条把白色区域隔开。你拿一支红色墨水笔，点在某个白色区域——墨水会沿着这个区域扩散，直到碰到黑色线条才停住。墨水只会染湿相同颜色的区域（白色），不会跳过黑色线条。Flood Fill 就是模拟这个过程。

在程序里，“墨水”就是我们要填充的新颜色，“纸张”就是二维网格，“黑色线条”是颜色不同的格子（比如值为1），“白色区域”是颜色相同且连通的格子（比如值为0）。

核心思路：递归的深度优先搜索（DFS）

Flood Fill 最常见的实现方式是利用深度优先搜索。过程很简单：

从起点格子 (sr, sc) 开始。
如果当前格子颜色等于旧颜色（要被替换的颜色），就把它的颜色改成新颜色。
然后递归地检查它的上下左右四个邻居，重复第2步。
如果格子颜色不是旧颜色，或者越界了，就直接返回，不继续搜。

关键点是：改颜色要发生在递归之前，否则可能会重复访问同一个格子（比如邻居反过来又访问自己），导致死循环。先改颜色，然后再去访问邻居，这样每个格子只会被处理一次。

完整代码示例（DFS 实现）

下面是一个完整的程序，它读入一个二维网格（数字表示颜色），然后执行 Flood Fill。代码中的变量都用简短英文单词，每行变量定义写中文注释。

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

vector<vector<int>> grid;  // 全局网格，存储颜色值

// floodFill函数：从 (row, col) 开始，把 oldColor 全部改成 newColor
void floodFillDFS(int row, int col, int oldColor, int newColor) {
    // 边界检查：行或列超出网格范围，直接返回
    if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size())
        return;
    // 颜色检查：当前格子颜色不是旧颜色，不需要填充，返回
    if (grid[row][col] != oldColor)
        return;

    // 修改当前格子颜色为新颜色
    grid[row][col] = newColor;

    // 递归填充四个方向：上、下、左、右
    floodFillDFS(row - 1, col, oldColor, newColor);  // 上
    floodFillDFS(row + 1, col, oldColor, newColor);  // 下
    floodFillDFS(row, col - 1, oldColor, newColor);  // 左
    floodFillDFS(row, col + 1, oldColor, newColor);  // 右
}

int main() {
    int rows, cols;               // 网格的行数和列数
    cin >> rows >> cols;          // 例如输入：3 3
    // 调整网格大小，所有元素初始为0
    grid.resize(rows, vector<int>(cols));
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cin >> grid[i][j];    // 读入每个格子的颜色（0或1等）
        }
    }

    int startRow, startCol, newColor;  // 起始行列和新颜色
    cin >> startRow >> startCol >> newColor;  // 例如：1 1 2
    int oldColor = grid[startRow][startCol];  // 记录起点原来的颜色
    if (oldColor != newColor) {               // 如果新颜色和旧颜色相同，就不用填充了
        floodFillDFS(startRow, startCol, oldColor, newColor);
    }

    // 输出填充后的网格
    for (auto &rowVec : grid) {
        for (int val : rowVec) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}

运行示例：不要被“对角线”迷惑

假设输入一个 3×3 网格：

意思是：行3，列3；然后读入9个数字；最后起点(1,1)，新颜色2。

起点 (1,1) 的颜色是1（oldColor = 1）。也就是说我们要把所有和 (1,1) 上下左右相邻且颜色为1的格子变成2。

从 (1,1) 出发，改颜色为2。
检查上 (0,1) 颜色为0，不是1，跳过。
下 (2,1) 颜色为0，跳过。
左 (1,0) 颜色为0，跳过。
右 (1,2) 颜色为1，递归进入 (1,2)。
在 (1,2) 改颜色为2，然后检查它的邻居：
- 上 (0,2) 颜色为1，递归进入 (0,2) → 改颜色为2，它的邻居都不再是1（左(0,1)=0，下(1,2)已经被改为2但不会重复处理），结束。
- 下 (2,2) 颜色为0，跳过。
- 左 (1,1) 已经是新颜色2，但 oldColor 是1，grid[1][1] != 1 所以直接返回（不会死循环）。
- 右越界，跳过。

最终网格变成：

0 0 2
0 2 2
0 0 0

注意，格子 (0,0) 虽然也是0，但它和 (1,1) 的 1 区域不相邻（中间隔着0或边界），所以没有被填充。

容易混淆的地方：很多人以为 Flood Fill 会“按对角线扩散”，比如 (1,1) 和 (0,0) 虽然相邻在对角线上，但标准实现只考虑上下左右。如果题目要求八方向（包括对角线），只需在递归时再添加四个方向：(r-1,c-1), (r-1,c+1), (r+1,c-1), (r+1,c+1)。

新手容易犯的错误

忘记检查边界
递归时如果不判断 row < 0 等，会导致数组越界，程序崩溃。一定要在函数开头顶部做边界检查。
没有比较 oldColor 和 newColor
如果 newColor 正好等于 oldColor，那整个递归会无限循环吗？不会，因为递归前有一句 if (oldColor != newColor) 保证了不会进入。但如果忘了这一步，递归进去后，grid[r][c] != oldColor 永远为 false（因为已经改成 newColor），实际上会立刻返回，但会浪费函数调用。更严重的问题是：如果 newColor == oldColor，整个区域不会被改变，但递归还是会执行一遍，白白消耗时间。所以加这个判断是好的习惯。
递归方向搞反
比如只填充了左右，忘了上下；或者方向顺序写错，但没关系，只要四个方向都覆盖即可。
全局变量或参数传递问题
如果 grid 不是全局变量，而是作为参数传入，记得用引用（vector<vector<int>>&），否则会复制整个网格，性能很低，且递归中的修改不会影响实参。

另一种实现：广度优先搜索（BFS）

DFS 用递归，代码简洁，但缺点是在网格很大时可能导致函数调用栈溢出（比如递归深度等于格子数）。这时可以用队列实现 BFS（广度优先搜索），一层一层地扩散。

BFS 思路：从起点开始，把起点入队；只要队列不空，取出队首格子，改颜色，然后把它上下左右四个方向中颜色为 oldColor 且没被处理过的邻居入队。注意同样需要先改颜色再入队，防止重复入队。

BFS 的代码大致如下（只展示核心函数）：

#include <queue>

void floodFillBFS(int startRow, int startCol, int oldColor, int newColor) {
    if (oldColor == newColor) return;
    queue<pair<int,int>> q;
    q.push({startRow, startCol});
    grid[startRow][startCol] = newColor;  // 把起点改为新颜色再入队？这里先改掉

    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        // 邻居数组
        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < grid.size() && nc >= 0 && nc < grid[0].size() 
                && grid[nr][nc] == oldColor) {
                grid[nr][nc] = newColor;  // 先改颜色再入队
                q.push({nr, nc});
            }
        }
    }
}

DFS 和 BFS 的选择：DFS 代码简洁（递归），适合小规模场景（比如几百个格子）；BFS 用队列，不会栈溢出，适合超大网格（比如 1000×1000）。两种方法都能正确完成填充。