多源 BFS 算法详解与经典题目实战

飞地的数量

题目要求统计无法通过上下左右移动到达边界的所有 1 的数量。

这其实是一个反向思维的问题。与其找哪些 1 走不到边界，不如先找出所有能走到边界的 1。我们可以从边界上的 1 开始进行 BFS，标记所有能连通到边界的陆地。最后剩下的未被标记的 1，就是我们要找的飞地。

实现时，先遍历网格边缘，将边缘上的 1 和所有的 0 都标记为已访问并入队（0 本身不可达，但也作为障碍处理）。然后执行 BFS，每访问一个新的 1，就减少计数。最终剩余的计数即为答案。

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

    public int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] flag = new boolean[m][n];
        int ret = m * n;

        // 边界上的 1 入队，并标记；0 也标记
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && (i == 0 || i == m - 1 || j == 0 || j == n - 1)) {
                    queue.add(new int[]{i, j});
                    flag[i][j] = true;
                    ret--;
                } else if (grid[i][j] == 0) {
                    flag[i][j] = true;
                    ret--;
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = arr[0] + dx[i];
                int y = arr[1] + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && !flag[x][y]) {
                    ret--;
                    queue.add(new int[]{x, y});
                    flag[x][y] = true;
                }
            }
        }
        return ret;
    }
}

地图中的最高点

给定水域（1）和陆地（0），要求给每个格子分配高度，使得相邻格子高度差不超过 1，且高度尽可能大。

这本质上还是求最短距离的问题。水域的高度定为 0，然后像水波一样向外扩散，每扩散一层高度加 1。这与 01 矩阵的思路完全一致，只是初始状态不同：这次是将所有水域入队，陆地初始化为 -1 表示未访问。

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

    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length;
        int n = isWater[0].length;
        int[][] height = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();

        // 水域高度为 0 并入队，陆地初始化为 -1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                height[i][j] = -1;
                if (isWater[i][j] == 1) {
                    height[i][j] = 0;
                    queue.add(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = arr[0] + dx[i];
                int y = arr[1] + dy[i];
                // 高度为 -1 表示未访问
                if (x >= 0 && x < m && y >= 0 && y < n && height[x][y] == -1) {
                    height[x][y] = height[arr[0]][arr[1]] + 1;
                    queue.add(new int[]{x, y});
                }
            }
        }
        return height;
    }
}

地图分析

找出海洋（0）到最近陆地（1）的最大距离。

这是最典型的多源 BFS 应用。我们将所有陆地坐标一次性加入队列，然后向外扩展。记录 BFS 的层数，当所有海洋都被访问到时，最后的层数即为最大距离。需要注意的是，如果全为陆地或全为海洋，应返回 -1。

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

    public int maxDistance(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ret = 0;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] flag = new boolean[m][n];

        // 所有 1 入队
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.add(new int[]{i, j});
                    flag[i][j] = true;
                    ret++;
                }
            }
        }

        // 判断是否全 0 或全 1
        if (ret == 0 || ret == m * n) return -1;
        ret = -1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            ret++;
            while (size-- != 0) {
                int[] arr = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int x = arr[0] + dx[i];
                    int y = arr[1] + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && !flag[x][y] && grid[x][y] == 0) {
                        queue.add(new int[]{x, y});
                        flag[x][y] = true;
                    }
                }
            }
        }
        return ret;
    }
}

通过以上四个例子可以看出，多源 BFS 的关键在于起点的选择。只要将符合条件的起点全部放入队列，后续的层序遍历就能自然计算出全局的最优解。在实际编码中，注意处理好边界条件和初始化状态，就能避免很多不必要的错误。