多源 BFS：从单源到多源的优化思路与实战

这里用 ret 数组本身充当了标记数组，既节省空间又简化逻辑。当 ret[x][y] 为 -1 时，说明该位置尚未被访问，更新后即为当前层数加一。

1020. 飞地的数量

问题描述：统计无法到达边界（上下左右边缘）的 1 的数量。

思路分析

这道题可以看作是多源 BFS 的逆向思维。与其找内部的 1，不如从边界出发，把所有能连通的 1 标记掉。剩下的未被标记的 1 就是飞地。

具体步骤：

1. 遍历边界，将所有值为 1 的坐标入队并标记。
2. 对边界上的 1 执行 BFS，标记所有能到达的内部 1。
3. 最后统计未被标记的 1 的数量。

代码实现

import java.util.LinkedList;
import java.util.Queue;

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;
        boolean[][] flag = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        int ret = m * n;

        // 边界处理：将边界上的 1 入队并标记
        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--;
                }
            }
        }

        // BFS 标记所有与边界相连的 1
        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]) {
                    flag[x][y] = true;
                    queue.add(new int[]{x, y});
                    ret--;
                }
            }
        }
        return ret;
    }
}

1765. 地图中的最高点

问题描述：给定水域（1）和陆地（0），要求返回高度矩阵，使得相邻格子高度差不超过 1，且高度尽可能大。

思路分析

这其实是一个典型的多源 BFS 求距离问题。所有水域的高度初始化为 0，然后像水波一样向外扩散，每扩散一层高度加 1。由于是从所有水域同时开始，最终得到的就是满足条件的最大高度分布。

代码实现

import java.util.LinkedList;
import java.util.Queue;

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

        // BFS 扩散
        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 && height[x][y] == -1) {
                    height[x][y] = height[arr[0]][arr[1]] + 1;
                    queue.add(new int[]{x, y});
                }
            }
        }
        return height;
    }
}

1162. 地图分析

问题描述：找出海洋（0）到最近陆地（1）的最大距离。

思路分析

这是多源 BFS 最直接的应用之一。我们将所有陆地作为起点入队，向外扩散直到覆盖所有海洋。记录扩散的层数，最后一层的深度即为答案。

注意特判：如果全是陆地或全是海洋，应返回 -1。

代码实现

import java.util.LinkedList;
import java.util.Queue;

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;
        // BFS 层序遍历
        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) {
                        flag[x][y] = true;
                        queue.add(new int[]{x, y});
                    }
                }
            }
        }
        return ret;
    }
}

总结

多源 BFS 的核心在于起点的初始化。只要将问题抽象为'从一组点出发，求其他点到这组点的最短距离'，就可以套用这个模板。关键点包括：

• 使用队列存储所有初始起点。
• 利用距离数组或标记数组避免重复访问。
• 层序遍历时记录步数或距离。

掌握这个模式，面对类似的网格距离、连通性分析问题时，就能快速找到解题方向。