BFS 解决 FloodFill 算法：从图像渲染到岛屿问题实战 | 极客日志

Javajava算法

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

BFS 算法在 FloodFill 场景下的应用。涵盖图像渲染、岛屿数量及最大面积、被围绕区域四个经典 LeetCode 题目。通过队列实现广度优先搜索，标记访问状态，处理连通性问题。重点在于边界检查、颜色/字符匹配及避免重复遍历。Java 实现示例展示如何优化时空复杂度，适用于网格类图论问题。

莫名其妙发布于 2026/3/27更新于 2026/4/232 浏览

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, };

             (   ; i < ; i++) {
                   x + dx[i];
                   y + dy[i];

                
                 (nx >=  && nx < image.length && 
                    ny >=  && ny < image[].length && 
                    pre == image[nx][ny]) {
                    image[nx][ny] = color;
                    queue.add( []{nx, ny});
                }
            }
        }
         image;
    }
}

// 时间复杂度：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});
                }
            }
        }
    }
}

// 时间复杂度：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;
    }
}

// 时间复杂度：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;
                }
            }
        }
    }
}