Flood Fill 洪水填充算法：经典题型实战与总结

Flood Fill 算法概述

Flood Fill（洪水填充）是图论中处理连通块问题的基础算法。核心思想是通过 DFS 或 BFS 遍历具有相同性质的相邻节点，将其归为一类并执行相应操作。在网格问题中，这通常意味着从起点出发，向上下左右四个方向扩展，直到遇到边界或不同性质的节点。

图像渲染

这是最典型的 Flood Fill 应用。给定一个二维矩阵代表图像，以及起始坐标和新的颜色值，要求将起始点所在的连通区域全部染成新颜色。

关键点：

1. 记录原始颜色值，只有当邻居颜色等于原始颜色时才继续递归。
2. 死循环陷阱： 如果起始点的颜色已经等于目标颜色，直接返回原矩阵。否则程序会陷入无限递归，因为当前点会被标记为目标色，但逻辑上它仍满足'颜色相同'的条件，导致反复访问。

class Solution {
public:
    int m, n;
    int originalColor; // 记录需要修改的原始颜色

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        originalColor = image[sr][sc];
        m = image.size();
        n = image[0].size();

        // 避免死循环：如果起始点已经是目标颜色，无需修改
        if (originalColor == color) return image;

        dfs(image, sr, sc, color);
        return image;
    }

    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 = dx[k] + i;
            int y = dy[k] + j;
            // 检查边界且颜色匹配
            if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == originalColor) {
                dfs(image, x, y, color);
            }
        }
    }
};

岛屿数量

给定由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。岛屿被水包围，且通过水平或垂直方向相连。

思路： 遍历整个网格，一旦发现 '1'，说明发现了一个新岛屿，计数器加一。然后立即启动 DFS，将该岛屿所有相连的 '1' 都标记为 '0'（海水），这样后续遍历时就不会重复统计。

class Solution {
public:
    int m, n;
    int count = 0;

    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        m = grid.size();
        n = grid[0].size();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};

    void dfs(vector<vector<char>>& grid, int i, int j) {
        // 将访问过的陆地标记为水，防止重复访问
        grid[i][j] = '0';
        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 && grid[x][y] == '1') {
                dfs(grid, x, y);
            }
        }
    }
};

岛屿的最大面积

在岛屿数量的基础上，我们需要计算每个岛屿包含的格子数，并找出最大值。

思路： 使用 visited 数组标记已访问的格子。每次遇到未访问的陆地，重置当前面积计数器，DFS 过程中每访问一个有效格子就累加面积。遍历结束后更新全局最大值。

class Solution {
public:
    int m, n;
    int maxArea = 0;
    int currentArea = 0;
    bool vis[51][51];

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if (grid.empty()) return 0;
        m = grid.size();
        n = grid[0].size();
        memset(vis, 0, sizeof(vis));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!vis[i][j] && grid[i][j] == 1) {
                    currentArea = 0;
                    dfs(grid, i, j);
                    maxArea = max(maxArea, currentArea);
                }
            }
        }
        return maxArea;
    }

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    void dfs(vector<vector<int>>& grid, int i, int j) {
        vis[i][j] = true;
        currentArea++;
        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);
            }
        }
    }
};

被围绕的区域

给定一个二维矩阵，其中包含 'O' 和 'X'。要求将所有被 'X' 围绕的 'O' 替换为 'X'。

思路： 正难则反。直接找被围绕的 'O' 很难判断是否连通到边界。不如先找到所有与边界相连的 'O'，将它们标记为特殊字符（如 '.'）。最后，矩阵中剩余的 'O' 必然是被围绕的，将其改为 'X'；而标记为 '.' 的还原为 'O'。

class Solution {
public:
    int m, n;
    void solve(vector<vector<char>>& board) {
        if (board.empty()) return;
        m = board.size();
        n = board[0].size();

        // 1. 从四条边界的 'O' 开始 DFS，标记所有连通的 'O'
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') dfs(board, 0, j);
            if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
        }

        // 2. 遍历矩阵，'.' 还原为 'O'，剩余的 'O' 改为 'X'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '.') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    void dfs(vector<vector<char>>& board, int i, int j) {
        board[i][j] = '.';
        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 && board[x][y] == 'O') {
                dfs(board, x, y);
            }
        }
    }
};

太平洋大西洋水流问题

给定一个非负整数矩阵表示高度，水可以从高处流向低处或相等高度。求哪些格子既能流向太平洋，又能流向大西洋。

思路： 正向搜索容易超时且逻辑复杂。采用反向思维：从海洋边缘向内陆搜索。分别维护两个布尔矩阵 pacific 和 atlantic，记录从对应海洋能到达的格子。最后取交集即可。

class Solution {
public:
    int m, n;
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<int>> ret;
        if (heights.empty()) return ret;
        m = heights.size();
        n = heights[0].size();

        vector<vector<bool>> pac(m, vector<bool>(n, false));
        vector<vector<bool>> atl(m, vector<bool>(n, false));

        // 从太平洋边界（左、上）和大西洋边界（右、下）开始 DFS
        for (int j = 0; j < n; j++) {
            dfs(heights, 0, j, pac);
            dfs(heights, m - 1, j, atl);
        }
        for (int i = 0; i < m; i++) {
            dfs(heights, i, 0, pac);
            dfs(heights, i, n - 1, atl);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pac[i][j] && atl[i][j]) {
                    ret.push_back({i, j});
                }
            }
        }
        return ret;
    }

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    void dfs(vector<vector<int>>& heights, int i, int j, vector<vector<bool>>& ocean) {
        ocean[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 && 
                heights[i][j] <= heights[x][y] && !ocean[x][y]) {
                dfs(heights, x, y, ocean);
            }
        }
    }
};

扫雷游戏

模拟扫雷游戏的点击逻辑。如果点到地雷显示 'X'，如果点到空地显示周围地雷数，如果是空白格则自动展开。

思路：

1. 检测点击位置是否为地雷 'M'，是则直接变 'X' 结束。
2. 否则统计周围 8 个方向的地雷数。如果有地雷，显示数字并停止。
3. 如果没有地雷，显示 'B'，并递归展开周围 8 个方向的空白格 'E'。

class Solution {
public:
    int m, n;
    int dx[8] = {-1, 1, 0, 0, 1, 1, -1, -1};
    int dy[8] = {0, 0, -1, 1, 1, -1, 1, -1};

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size();
        n = board[0].size();
        int x = click[0], y = click[1];

        if (board[x][y] == 'M') {
            board[x][y] = 'X';
            return board;
        }

        dfs(board, x, y);
        return board;
    }

    void dfs(vector<vector<char>>& board, int i, int j) {
        int count = 0;
        // 统计周围地雷数
        for (int k = 0; k < 8; k++) {
            int x = dx[k] + i;
            int y = dy[k] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {
                count++;
            }
        }

        if (count > 0) {
            board[i][j] = count + '0';
        } else {
            board[i][j] = 'B';
            for (int k = 0; k < 8; k++) {
                int x = dx[k] + i;
                int y = dy[k] + j;
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') {
                    dfs(board, x, y);
                }
            }
        }
    }
};

衣橱整理

机器人从 (0,0) 出发，只能向右或向下移动。限制条件是坐标数位之和不能超过 k。求能到达多少个格子。

思路： 这是一个典型的 DFS 计数问题。注意数位和的计算方式，以及只能向右或向下移动的限制（相比其他题目减少了搜索方向）。使用 visited 数组避免重复访问。

class Solution {
public:
    int m, n;
    int count = 0;
    bool vis[101][101];

    int wardrobeFinishing(int _m, int _n, int cnt) {
        m = _m;
        n = _n;
        dfs(0, 0, cnt);
        return count;
    }

    int dx[2] = {1, 0};
    int dy[2] = {0, 1};

    void dfs(int i, int j, int cnt) {
        for (int k = 0; k < 2; k++) {
            int x = dx[k] + i;
            int y = dy[k] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
                if (digitSum(x) + digitSum(y) <= cnt) {
                    count++;
                    vis[x][y] = true;
                    dfs(x, y, cnt);
                }
            }
        }
    }

    int digitSum(int n) {
        int sum = 0;
        while (n) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
};

总结

通过这一系列题目，我们可以总结出 Flood Fill 算法的几个核心要点：

1. 正难则反： 在处理复杂约束时（如被围绕区域、水流问题），尝试反向思考往往能简化逻辑。例如从边界向内标记，而不是从内部向外寻找。
2. 连通块本质： 无论是图像渲染还是岛屿统计，本质上都是在寻找性质相同的连通分量。DFS 是最自然的实现方式，BFS 同样适用。
3. 细节决定成败： 注意边界条件检查、避免死循环（如起始点颜色不变的情况）、合理使用标记数组防止重复访问。
4. 方向控制： 根据题目要求灵活调整搜索方向（4 方向、8 方向或特定方向），代码结构可复用，只需修改方向数组即可。