Flood Fill 算法详解：DFS/BFS 实现与经典应用

Flood Fill 算法：数字世界的颜料蔓延术

算法本质 一种用于填充连通区域的经典算法，通过指定起点和填充规则，像倒颜料般自动填满封闭区域。

核心思想

1. 选定起点：从像素/网格的某个点出发
2. 扩散规则：
   • 4 连通：上下左右 4 个方向
   • 8 连通：增加斜向共 8 个方向（更易漏边）
3. 停止条件：遇到边界色或已填充区域

两种经典实现

基础版（DFS 递归实现）

#include <vector>
#include <iostream>
using namespace std;
// 4 方向移动：上右下左
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
void dfs(vector<vector<int>>& image, int x, int y, int oldColor, int newColor) {
    // 边界检查 + 颜色检查
    if(x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || image[x][y] != oldColor || image[x][y] == newColor) return;
    image[x][y] = newColor;
    // 填充新颜色
    // 递归 4 个方向
    for(int i = 0; i < 4; ++i) {
        dfs(image, x + dx[i], y + dy[i], oldColor, newColor);
    }
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    int oldColor = image[sr][sc];
    if(oldColor != newColor) dfs(image, sr, sc, oldColor, newColor);
    return image;
}

优化版（BFS 队列实现）

#include <queue>
#include <utility>
// for pair
vector<vector<int>> floodFill_BFS(vector<vector<int>>& image, int sr, int sc, int newColor) {
    int oldColor = image[sr][sc];
    if(oldColor == newColor) return image;
    queue<pair<int, int>> q;
    q.push({sr, sc});
    image[sr][sc] = newColor;
    while(!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for(int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < image.size() && ny >= 0 && ny < image[0].size() && image[nx][ny] == oldColor) {
                image[nx][ny] = newColor;
                q.push({nx, ny});
            }
        }
    }
    return image;
}

实际应用场景

• 画图软件的油漆桶工具
• 游戏中的地图可达性判断
• 图像处理（背景替换/抠图）
• LeetCode「岛屿数量」「图像渲染」等题型

使用 Flood Fill 算法解决经典问题

经典例题：岛屿问题

思路： 直接遍历这个二维网格，遇到'1'，就对这个网格相邻的最多四个网格以及它们相邻的区域进行判断。因为一个网格重复判断是没有意义的，并且相邻的为'1'的网格视为一个网格。我们需要一个等大的 bool 类型的二维数组来一一对应二维网格中的某个网格是否已经被检查过。如果被检查过，则不用检查；如果没有被检查过，则需要对其以及其周边区域进行检查。这就是记忆化搜索，bool 类型的二维数组就相当于一个记忆存储器。此外，因为需要对周边相邻的四个方向检查，我们可以提前创建两个数组来模拟四个方向。

代码实现：

class Solution {
public:
    int m;
    int n;
    int ret;
    vector<vector<bool>> vis;
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();
        vis = vector<vector<bool>>(m, vector<bool>(n, false));
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '1') {
                    if(!vis[i][j]) {
                        ret++;
                        dfs(grid, i, j);
                    }
                }
            }
        }
        return ret;
    }
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {-1, 1, 0, 0};
    void dfs(vector<vector<char>>& grid, int i, int j) {
        vis[i][j] = true;
        for(int k = 0; k < 4; k++) {
            int x = dx[k] + i;
            int y = dy[k] + j;
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1')
                dfs(grid, x, y);
        }
    }
};

经典例题：图像渲染

思路： 这种问题一般大差不差，有了上面一题的基础，这道思路也很清晰。直接对目标节点进行判断，如果需要上色就上色，并且对其周围区域以及周围区域的周围区域判断即可。

代码实现：

class Solution {
public:
    int m;
    int n;
    int prev;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    void dfs(vector<vector<int>>& image, int i, int j, int color) {
        image[i][j] = color;
        for(int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y < n && y >= 0 && image[x][y] == prev) {
                dfs(image, x, y, color);
            }
        }
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if(color == image[sr][sc]) return image;
        m = image.size();
        n = image[0].size();
        prev = image[sr][sc];
        dfs(image, sr, sc, color);
        return image;
    }
};

经典例题：太平洋大西洋水流问题

思路： 题目要求我们输出既可以流向大西洋又可以流向太平洋的所有格子。一个格子要流向太平洋，就需要有一条可以递减格子路径到太平洋；一个格子要流向大西洋，就需要一条可以递减格子路径到大西洋。如例子中的 [2,2] 格子，它的右方向按照 5->3->1 递减，流向大西洋；它的左方向按照 5->4->2 递减，流向太平洋。所以，我们需要对一个格子进行深搜，在其周围找到一条通往大西洋、一条通往太平洋的路径。这是解题思路，但你落实下去，就会发现难得可怕。这时候，正面突破就行不通，我们就需要从其他方面思考一下：与其求一个格子同时到太平洋、大西洋，不如先判断一个格子上的水是否能到太平洋，再判断是否能到大西洋。两个的结果都是对的，则符合题目要求，输出即可。解题思路就变成：先找到所有水流能流向太平洋的格子，再找到所有水流能流向大西洋的格子，在遍历一次所有格子，如果一个格子满足上述两个条件，就是我们需要的格子！

代码实现：

class Solution {
public:
    int m = 0;
    int n = 0;
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    void dfs(int i, int j, vector<vector<bool>>& vis, vector<vector<int>>& heights) {
        vis[i][j] = true;
        for(int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x < m && x >= 0 && y < n && y >= 0 && !vis[x][y] && heights[i][j] <= heights[x][y]) {
                dfs(x, y, vis, heights);
            }
        }
    }
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size();
        n = heights[0].size();
        vector<vector<int>> re_value;
        vector<vector<bool>> atl(m, vector<bool>(n, false));
        vector<vector<bool>> pac(m, vector<bool>(n, false));
        for(int j = 0; j < n; j++) {
            dfs(0, j, pac, heights);
            dfs(m - 1, j, atl, heights);
        }
        for(int i = 0; i < m; i++) {
            dfs(i, 0, pac, heights);
            dfs(i, n - 1, atl, heights);
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(pac[i][j] && atl[i][j]) {
                    re_value.push_back({i, j});
                }
            }
        }
        return re_value;
    }
};

结语： Flood Fill 算法就像数字世界的水彩笔，用最简单的规则解决了区域填充的核心问题。从图像编辑软件的魔术棒到游戏地图的可达性判断，这个经典算法的应用远比我们看到的更广泛。在实际开发中，针对不同场景可能需要考虑内存优化、并行计算等进阶技巧。但无论形式如何变化，其核心思想始终如一：通过系统性的蔓延规则，完成区域的智能填充。当你下次使用绘图软件时，不妨想想背后这个精妙的算法。或许这就是编程的魅力——用简洁的代码逻辑，实现看似复杂的视觉魔法。继续探索吧，更多算法奇迹等着你去发现！