0.多源最短路问题（BFS默认是边权为1）
1.01矩阵
542. 01 矩阵 - 力扣（LeetCode）
class Solution {int[] dx = { 0, 0, -1, 1 };int[] dy = { 1, -1, 0, 0 };public int[][] updateMatrix(int[][] mat) {int m = mat.length, n = mat[0].length;// dist[i][j] == -1：标记当前位置没有被搜索过// dist[i][j] != -1：存的是最短距离int[][] dist = new int[m][n];for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)dist[i][j] = -1;Queue<int[]> q = new LinkedList<>();// 1. 把所有的源点加⼊到队列⾥⾯for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (mat[i][j] == 0) {dist[i][j] = 0;q.add(new int[] { i, j });}}// 2. ⼀层⼀层的往外扩while (!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for (int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {dist[x][y] = dist[a][b] + 1;q.add(new int[] { x, y });}}}return dist;}
}2.飞地的数量
1020. 飞地的数量 - 力扣（LeetCode）
正难则反：从边上的 1 开始搜索，把与边上 1 相连的联通区域全部标记⼀下；然后再遍历⼀遍矩阵，看看哪些位置的 1 没有被标记即可标记的时候，可以⽤「多源 bfs 」解决。
class Solution {int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };public int numEnclaves(int[][] grid) {int m = grid.length, n = grid[0].length;boolean[][] vis = new boolean[m][n];Queue<int[]> q = new LinkedList<>();// 1. 把边上的 1 全部加⼊到队列中for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {if (grid[i][j] == 1) {q.add(new int[] { i, j });vis[i][j] = true;}}// 2. 多源 bfswhile (!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for (int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 &&!vis[x][y]) {q.add(new int[] { x, y });vis[x][y] = true;}}}// 3. 提取结果int ret = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (grid[i][j] == 1 && !vis[i][j])ret++;return ret;}
}3.地图中的最高点
1765. 地图中的最高点 - 力扣（LeetCode）
class Solution {int[] dx = { 0, 0, -1, 1 };int[] dy = { 1, -1, 0, 0 };public int[][] highestPeak(int[][] isWater) {int m = isWater.length, n = isWater[0].length;int[][] dist = new int[m][n];for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)dist[i][j] = -1;Queue<int[]> q = new LinkedList<>();// 1. 所有的源点加⼊到队列⾥⾯for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (isWater[i][j] == 1) {q.add(new int[] { i, j });dist[i][j] = 0;}// 2. 多源 bfswhile (!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for (int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {dist[x][y] = dist[a][b] + 1;q.add(new int[] { x, y });}}}return dist;}
}4.地图分析
1162. 地图分析 - 力扣（LeetCode）
class Solution {int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };public int maxDistance(int[][] grid) {int m = grid.length, n = grid[0].length;int[][] dist = new int[m][n];for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)dist[i][j] = -1;Queue<int[]> q = new LinkedList<>();for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (grid[i][j] == 1) {dist[i][j] = 0;q.add(new int[] { i, j });}int ret = -1;while (!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for (int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {dist[x][y] = dist[a][b] + 1;q.add(new int[] { x, y });ret = Math.max(ret, dist[x][y]);}}}return ret;}
}
