BFS 解决 FloodFill 算法：从图像渲染到岛屿问题实战

FloodFill 算法的核心思想其实很直观，就像洪水蔓延一样，从一个点出发，向四周扩散，把连通且满足条件的区域全部覆盖。在图论和网格问题中，这通常对应着广度优先搜索（BFS）或深度优先搜索（DFS）。

733. 图像渲染

这道题是 FloodFill 最经典的入门应用。给定一个二维数组表示的图像，以及起始坐标和新颜色，要求将与起始点相连且颜色相同的像素全部修改为新颜色。

思路解析

本质上就是遍历所有与起点相连的同色像素。我们可以利用队列来存储待处理的坐标。每次取出一个坐标，检查其上下左右四个方向，如果邻居合法、颜色相同且未被处理过，就将其加入队列并修改颜色。

这里有个细节要注意：如果起始点的颜色本身就是目标颜色，直接返回原数组即可，避免无效操作。另外，边界检查必不可少，防止数组越界。

// 时间复杂度：O(N)，空间复杂度：O(N)
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        // 记录开始颜色
        int pre = image[sr][sc];
        // 如果初始颜色就是目标颜色，无需处理
        if (pre == color) return image;

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{sr, sc});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];

            // 检查上下左右四个方向
            int[] dx = {0, 0, 1, -1};
            int[] dy = {1, -1, 0, 0};

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 下标合法且颜色相同，进行传染
                if (nx >= 0 && nx < image.length && 
                    ny >= 0 && ny < image[0].length && 
                    pre == image[nx][ny]) {
                    image[nx][ny] = color;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
        return image;
    }
}

200. 岛屿数量

题目给出了一个由 '0'（水）和 '1'（陆地）组成的二维字符数组，要求计算岛屿的数量。岛屿被水平或垂直方向的 '1' 连接而成。

思路解析

我们需要遍历整个网格，每遇到一个未访问过的 '1'，就说明发现了一个新岛屿。此时启动一次 BFS，将这块岛屿上所有相连的 '1' 都标记为已访问，这样后续遍历时就不会重复计数了。

为了节省空间，我们通常使用一个 visited 布尔数组来记录状态，或者直接在原数组上将访问过的 '1' 改为 '0'。

// 时间复杂度：O(M*N)，空间复杂度：O(M*N)
class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    boolean[][] vis;

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        vis = new boolean[m][n];
        int ret = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 找到第一个未访问的 '1'，作为'登陆点'
                if (grid[i][j] == '1' && !vis[i][j]) {
                    bfs(grid, i, j, m, n);
                    ret++;
                }
            }
        }
        return ret;
    }

    private void bfs(char[][] grid, int x, int y, int m, int n) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        vis[x][y] = true;

        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = arr[0] + dx[i];
                int ny = arr[1] + dy[i];
                // 下标合法，字符为 '1'，且并没有被访问
                if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                    grid[nx][ny] == '1' && !vis[nx][ny]) {
                    vis[nx][ny] = true;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
    }
}

695. 岛屿的最大面积

这道题和上一题非常相似，区别在于需要计算每个岛屿包含的格子数，并返回最大值。

思路解析

在 BFS 遍历过程中，每弹出一个节点，面积计数器加一。遍历完当前岛屿后，更新全局最大面积即可。

// 时间复杂度：O(M*N)，空间复杂度：O(M*N)
class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    boolean[][] vis;

    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        vis = new boolean[m][n];
        int maxArea = 0;

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

    private int bfs(int[][] grid, int x, int y, int m, int n) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        vis[x][y] = true;
        int area = 0;

        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            area++;
            for (int i = 0; i < 4; i++) {
                int nx = arr[0] + dx[i];
                int ny = arr[1] + dy[i];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                    grid[nx][ny] == 1 && !vis[nx][ny]) {
                    vis[nx][ny] = true;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
        return area;
    }
}

130. 被围绕的区域

这道题稍微绕一点。给定一个由 'X' 和 'O' 组成的二维字符数组，要求将所有被 'X' 完全包围的 'O' 替换为 'X'。注意，边缘的 'O' 以及与边缘 'O' 相连的 'O' 不会被替换。

思路解析

与其思考哪些 'O' 会被包围，不如反过来想：哪些 'O' 是安全的？显然是那些能连接到边界的 'O'。因此，策略变为：

1. 遍历四条边上的所有元素，如果发现 'O'，就从该点开始 BFS/DFS，将所有连通的 'O' 标记为特殊状态（比如用临时字符或布尔数组）。
2. 遍历整个矩阵，将没有被标记的 'O' 改为 'X'，将标记过的恢复为 'O'（或者直接保留标记后的逻辑）。

这种逆向思维在网格问题中非常常见，能有效降低判断复杂度。

// 时间复杂度：O(M*N)，空间复杂度：O(M*N)
class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    boolean[][] flag;
    int m, n;

    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        m = board.length;
        n = board[0].length;
        flag = new boolean[m][n];

        // 只遍历边缘字符元素
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 如果是边缘且为 'O'，则进行宽搜标记
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) &&
                    board[i][j] == 'O' && !flag[i][j]) {
                    bfs(board, i, j);
                }
            }
        }

        // 将被包围的字符改为 X
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O' && !flag[i][j]) {
                    board[i][j] = 'X';
                }
            }
        }
    }

    // 宽搜符合条件的不被包围字符
    private void bfs(char[][] board, int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        flag[x][y] = true;

        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = arr[0] + dx[i];
                int ny = arr[1] + dy[i];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                    board[nx][ny] == 'O' && !flag[nx][ny]) {
                    queue.add(new int[]{nx, ny});
                    flag[nx][ny] = true;
                }
            }
        }
    }
}