本次的三道题都用了多源点BFS的方法，关于什么是多源点BFS呢，就是求很多个起点到一个终点的关系，就将终点入队，反过来求。如下面三道题：

542. 01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/01-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

这道题要求的是每一个1离最近0的距离，那么可以假设这个矩阵就只有一个0，其余的都是1，就是多源点BFS问题，所以就将所有的0入队，然后开始用BFS来计算。

用一个新的dist矩阵来记录每一个1距离最近的0的距离。

class Solution {
    // 方向
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length,n = mat[0].length;
        // 记录已访问的节点
        boolean[][] visited = new boolean[m][n];
        // 初始队列
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                // 所有0全部入队
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }

        // 记录距离
        int[][] dist = new int[m][n];
        // 搜索0位置的四周，并记录距离
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int row = cur[0], cln = cur[1];
            for (int i = 0; i < 4; i++) {
                int ni = row + dirs[i][0];
                int nj = cln + dirs[i][1];
                if (ni >= 0 && nj >= 0 && ni < m &&  nj < n && !visited[ni][nj]) {
                    dist[ni][nj] = dist[row][cln] + 1;
                    queue.offer(new int[]{ni, nj});
                    visited[ni][nj] = true;
                }
            }
        }

        return dist;
    }
}

结果如下：

1162. 地图分析

你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

如果网格上只有陆地或者海洋，请返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

这道题跟上面是同样的方法，只不过是找到0距离最近的1的距离，所以就将所有的1入队，然后进行BFS算法。

注意需要判断全1或者全0的情况，就只用判断队列的长度是否为m*n或者0。

class Solution {
    // 方向
    static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int maxDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // 初始队列
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                } else {
                    grid[i][j] = -1;
                }
            }
        }
        // 如果全为陆地或嗨哟
        if (queue.size() == m * n || queue.size() == 0) return -1;
        // BFS
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int row = cur[0], cln = cur[1];
            for (int i = 0; i < 4; i++) {
                int newRow = row + dirs[i][0];
                int newCln = cln + dirs[i][1];
                if (newRow < 0 || newCln < 0 || newRow >= m || newCln >= n || grid[newRow][newCln] > 0) continue;
                grid[newRow][newCln] = grid[row][cln] + 1;
                // 周围节点入队
                queue.offer(new int[]{newRow, newCln});
            }
        }

        int maxDist = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxDist = Math.max(maxDist, grid[i][j]);
            }
        }

        return maxDist - 1;
    }
}

结果如下：

994. 腐烂的橘子

在给定的网格中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotting-oranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

一样的思想，腐烂的橘子先入队，然后影响周围的橘子。

需要判断的是没有橘子，即全0的情况，就用一个参数计数。

class Solution {
    public static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        int countZero = 0;
        // 初始队列
        Queue<int[]> queue = new LinkedList<>();
        // 所有腐烂橘子入队
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
                // 考虑0的情况
                if (grid[i][j] == 0) {
                    countZero++;
                }
            }
        }
        // 如果没有橘子
        if (countZero == m * n) return 0;

        int time = 0;
        // BFS将所有腐烂橘子四周的橘子腐烂
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int row = cur[0], cln = cur[1];
                // 四周橘子腐烂
                for (int j = 0; j < 4; j++) {
                    int newRow = row + dirs[j][0];
                    int newCln = cln + dirs[j][1];
                    // 出界或者周围不是新鲜橘子，continue
                    if (newRow < 0 || newCln < 0 || newRow >= m || newCln >= n || grid[newRow][newCln] != 1) continue;
                    grid[newRow][newCln] = 2;
                    queue.offer(new int[]{newRow, newCln});
                }
            }
            // 更新时间
            time++;
        }

        // 判断是否还有新鲜橘子
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) return -1;
            }
        }
        
        return time - 1;
    }
}

结果如下：