本次的三道题都用了多源点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;
}
}
结果如下：
