BFS 算法专题（四）：多源 BFS

目录

1. 01 矩阵

1.1 算法原理

1.2 算法代码

2. 飞地的数量

2.1 算法原理

2.2 算法代码

3. 地图中的最高点

3.1 算法原理

3.2 算法代码

4. 地图分析

4.1 算法原理

4.2 算法代码

---

1. 01 矩阵

. - 力扣（LeetCode）

1.1 算法原理

1. 采用 BFS + 正难则反 的解题思想, 把所有为 0 的位置为起点, 把所有为 1 的位置为终点.
2. 将所有为 0 的位置加入队列中, 一层一层往外扩, 将为 1 的位置, 修改为距离 0 的最短步数

细节点: 建立一个二维数组 int[][] distance, distinct[i][j] 中存的是 [i, j] 位置距离 0 的最短路径.

dest数组的作用:

1. 不需使用 boolean 数组做标记 => 将原数组中为 1 的位置, 在 dest 中初始化为 -1(特殊标记)
2. 不需使用 size 记录每层中元素个数 => 借助 dest[a][b] 中的值即可(dest[x, y] = dest[a, b] + 1)
3. 不需使用 step 记录扩展的层数 => 借助 dest[a][b] 中的值即可(dest[x, y] = dest[a, b] + 1)

1.2 算法代码

class Solution {public int[][] updateMatrix(int[][] mat) {int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};int m = mat.length, n = mat[0].length;int[][] dist = new int[m][n];Queue<int[]> q = new LinkedList<>();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(mat[i][j] == 0) q.offer(new int[]{i, j});else dist[i][j] = -1;}}// 以为 0 位置为起点, 一层一层往外扩while(!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for(int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {dist[x][y] = dist[a][b] + 1;q.offer(new int[]{x, y});}}}return dist;}
}

---

2. 飞地的数量

. - 力扣（LeetCode）

2.1 算法原理

正难则反 + 多源 BFS

1. 将边界上的 1 进行入队操作
2. 以边界上的 1 为起点, 进行多源 BFS, 将和其连通的其他的 1 进行标记.
3. 最终, 返回内部未被标记的 1 的个数

 

2.2 算法代码

class Solution {public int numEnclaves(int[][] grid) {int m = grid.length, n = grid[0].length;int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};boolean[][] check = new boolean[m][n];Queue<int[]> q = new LinkedList<>();// 将边界上的 1 入队列for(int i = 0; i < m; i++) {if(grid[i][0] == 1) q.offer(new int[]{i, 0});if(grid[i][n - 1] == 1) q.offer(new int[]{i, n - 1});}for(int j = 0; j < n; j++) {if(grid[0][j] == 1) q.offer(new int[]{0, j});if(grid[m - 1][j] == 1) q.offer(new int[]{m - 1, j});}// 多源 BFS: 将和边界上连通的 1 进行标记while(!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];check[a][b] = true;for(int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !check[x][y]) {check[x][y] = true;q.offer(new int[]{x, y});}}}// 统计内部不连通的 1 的个数int ret = 0;for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) if(grid[i][j] == 1 && !check[i][j]) ret++;}return ret;}
}

---

3. 地图中的最高点

. - 力扣（LeetCode）

3.1 算法原理

1. 由于任意相邻的格子高度差 至多 为 1, 所以应以水域位置为起点(水域位置固定高度为 0), 进行多源 BFS
2. 将水域位置加入队列, 一层一层往外扩展.
3. 每扩展到一个位置, 这个位置上的高度, 应为上个位置的高度 +1(求最高高度, 要求高度差不超过 1)

3.2 算法代码

class Solution {public int[][] highestPeak(int[][] isWater) {int m = isWater.length, n = isWater[0].length;int[][] height = new int[m][n];for(int i = 0; i < m; i++) Arrays.fill(height[i], -1);Queue<int[]> q = new LinkedList<>();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(isWater[i][j] == 1) {height[i][j] = 0;q.offer(new int[]{i, j});}}}int[] dx = {1, -1, 0, 0};int[] dy = {0, 0 ,1, -1};while(!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for(int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && height[x][y] == -1) {height[x][y] = height[a][b] + 1;q.offer(new int[]{x, y});}}}return height;}
}

---

4. 地图分析

. - 力扣（LeetCode）

4.1 算法原理

1. 依旧是 正难则反 + BFS

2. 创建一个 dist 数值, 将陆地位置初始化为 0 

3. 以陆地位置为起点, 向外扩展, 扩展到的海洋位置的值是原来位置的值的基础上 +1(dist[x][y] = dist[a][b] + 1)

4. dist 数组中的最大值, 就是海洋距离陆地的最远位置

4.2 算法代码

class Solution {public int maxDistance(int[][] grid) {int m = grid.length, n = grid[0].length;int[][] dist = new int[m][n];Queue<int[]> q = new LinkedList<>();for(int i = 0; i < m; i++) Arrays.fill(dist[i], -1);// 将陆地在 dist 中的位置初始化为 0// 并入队boolean sea = false;boolean ground = false;for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == 1) {dist[i][j] = 0;q.offer(new int[]{i, j});}if(grid[i][j] == 0) sea = true;if(grid[i][j] == 1) ground =true;}}if(!sea || !ground) return -1;int[] dx = {1, -1, 0, 0};int[] dy = {0 ,0 , 1, -1};int ret = 0;while(!q.isEmpty()) {int[] t = q.poll();int a = t[0], b = t[1];for(int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {dist[x][y] = dist[a][b] + 1;q.offer(new int[]{x, y});ret = Math.max(ret, dist[x][y]);}}}return ret;}
}

---

END