BFS_3">1. leetcode中BFS图论搜索题
leetcode链接：1162. 地图分析
你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。如果网格上只有陆地或者海洋，请返回 -1。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
示例一：
输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。
示例二：
输入：grid = [[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释：
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。
BFS_30">2. 单源 BFS
通常我们使用 BFS 求最短路，都是针对如下场景：从特定的起点出发，求解到达特定终点的最短距离。
这是一类特殊的「单源最短路」问题：本质是在一个边权为 1 的图上，求从特定「源点」出发到达特定「汇点」的最短路径。
对于本题，如果套用「单源最短路」做法，我们需要对每个「海洋」位置做一次 BFS：求得每个「海洋」的最近陆地距离，然后在所有的距离中取作为答案。
单次 BFS 的最坏情况需要扫描完整个矩阵，复杂度为 max。
同时，最多有 n^2 个海洋区域需要做 BFS，因此这样的做法复杂度为O(n ^ 4) ，并且O(n ^ 4)可直接取满。
PS. 数据范围为 10 ^ 2，理论上是一定会超时，但本题数据较弱，Java 2021/06/28 可过。
一些细节：为了方便，我们在使用哈希表记录距离时，将二维坐标 (x, y) 转化为对应的一维下标 idx = x * n + y 作为 key 进行存储。
代码实现：
class Solution {
public int maxDistance(int[][] grid) {
int n = grid.length;
int ans = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
ans = Math.max(ans, bfs(n, i, j, grid));
}
}
}
return ans;
}
// 单次 BFS：求解海洋位置 (x,y) 最近的陆地距离
public int bfs(int n, int x, int y, int[][] grid) {
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
Deque<int[]> queue = new ArrayDeque<>();
Map<Integer, Integer> map = new HashMap<>();
queue.addLast(new int[]{x, y});
map.put(x * n + y, 0);
while (!queue.isEmpty()) {
int[] poll = queue.pollFirst();
int dx = poll[0], dy = poll[1];
int step = map.get(dx * n + dy);
if (grid[dx][dy] == 1) return step;
for (int[] di : dirs) {
int nx = dx + di[0], ny = dy + di[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
int key = nx * n + ny;
if (map.containsKey(key)) continue;
queue.addLast(new int[]{nx, ny});
map.put(key, step + 1);
}
}
return -1;
}
}
BFS_86">3. 多源 BFS
这其实还是道「多源 BFS」入门题。
与「单源最短路」不同，「多源最短路」问题是求从「多个源点」到达「一个/多个汇点」的最短路径。
在实现上，最核心的搜索部分，「多源 BFS」与「单源 BFS」并无区别。
并且通过建立「虚拟源点」的方式，我们可以「多源 BFS」转换回「单源 BFS」问题。
什么意思？
以本题为例，题面要我们求每个「海洋」区域到最近的「陆地」区域的最大值。
我们可以将「源点/起点」和「汇点/终点」进行反转：从每个「陆地」区域出发，多个「陆地」区域每次同时向往扩散一圈，每个「海洋」区域被首次覆盖时所对应的圈数，就是「海洋」区域距离最近的「陆地」区域的距离。
不过，这是如何与「单源 BFS」联系起来的呢？
我们可以想象存在一个「虚拟源点」，其与所有「真实源点」（陆地）存在等权的边，那么任意「海洋」区域与「最近的陆地」区域的最短路等价于与「虚拟源点」的最短路：
实现上，我们并不需要真的将这个虚拟源点建立出来，只需要在 BFS 前将所有的「真实源点」进行入队即可。
这个过程相当于从队列中弹出「虚拟源点」，并把它所能到点（真实源点）进行入队，然后再进行常规的 BFS 。
一些细节：实现上为了方便，在进行常规 BFS 时，如果一个「海洋」区域被访问到，说明其被离它「最近的陆地」覆盖到了，修改值为最小距离。这样我们只需要考虑那些值仍然为的「海洋」区域即可（代表尚未被更新）。
代码实现：
class Solution {
public int maxDistance(int[][] grid) {
int n = grid.length;
Deque<int[]> d = new ArrayDeque<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
d.add(new int[]{i, j});
map.put(i * n + j, 0);
}
}
}
int ans = -1;
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
while (!d.isEmpty()) {
int[] poll = d.poll();
int dx = poll[0], dy = poll[1];
int step = map.get(dx * n + dy);
for (int[] di : dirs) {
int nx = dx + di[0], ny = dy + di[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (grid[nx][ny] != 0) continue;
grid[nx][ny] = step + 1;
d.add(new int[]{nx, ny});
map.put(nx * n + ny, step + 1);
ans = Math.max(ans, step + 1);
}
}
return ans;
}
}
不使用哈希表：
class Solution {
public int maxDistance(int[][] grid) {
// 多源BFS，从陆地开始向海洋扩散
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
Queue<int[]> queue = new ArrayDeque<>();
int n = grid.length;
// 先把所有的陆地都入队。
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
queue.offer(new int[] {i, j});
}
}
}
// 从各个陆地开始，一圈一圈的遍历海洋，最后遍历到的海洋就是离陆地最远的海洋。
boolean hasOcean = false;
int[] point = null;
while (!queue.isEmpty()) {
point = queue.poll();
int x = point[0], y = point[1];
// 取出队列的元素，将其四周的海洋入队。
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX < 0 || newX >= n || newY < 0 || newY >= n || grid[newX][newY] != 0) {
continue;
}
grid[newX][newY] = grid[x][y] + 1; // 这里我直接修改了原数组，因此就不需要额外的数组来标志是否访问
hasOcean = true;
queue.offer(new int[] {newX, newY});
}
}
// 没有陆地或者没有海洋，返回-1。
if (point == null || !hasOcean) {
return -1;
}
// 返回最后一次遍历到的海洋的距离。
return grid[point[0]][point[1]] - 1;
}
}
BFS_198">4. 多源BFS扩展
leetcode题目链接：1765. 地图中的最高点
题目描述：
给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由 陆地 和 水域 单元格组成的地图。
- 如果
isWater[i][j] == 0，格子(i, j)是一个 陆地 格子。 - 如果
isWater[i][j] == 1，格子(i, j)是一个 水域 格子。
你需要按照如下规则给每个单元格安排高度：
- 每个格子的高度都必须是非负的。
- 如果一个格子是是 水域 ，那么它的高度必须为 0 。
- 任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）
找到一种安排高度的方案，使得矩阵中的最高高度值 最大 。
请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回 任意一个 。
题解：
题目规定了水域区域的高度为 0，然后相邻格子之间的高度差至多为 1，
我们可以将所有水域（高度为 0）区域进行入队，然后跑一遍 BFS 即可。
将所有水域（高度为 0）区域进行入队的操作可看作是将与「虚拟源点」链接的节点进行入队（也等价于起始只将虚拟源点入队）：
容易证明这样做法的正确性：对于一个「陆地」区域（高度可变）而言，其所能填入的高度，取决于其距离其他「水域」区域的距离，而我们最终要让整个答案矩阵合法，因此每个「陆地」区域应该取其所能填入的高度的「下界」，即只由「距离它最近的水域」区域所更新，这符合 BFS 的性质。
代码实现：
class Solution {
public int[][] highestPeak(int[][] isWater) {
int m = isWater.length, n = isWater[0].length;
int[][] ans = new int[m][n];
Deque<int[]> d = new ArrayDeque<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (isWater[i][j] == 1) d.addLast(new int[]{i, j});
ans[i][j] = isWater[i][j] == 1 ? 0 : -1;
}
}
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
while (!d.isEmpty()) {
int[] info = d.pollFirst();
int x = info[0], y = info[1];
for (int[] di : dirs) {
int nx = x + di[0], ny = y + di[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (ans[nx][ny] != -1) continue;
ans[nx][ny] = ans[x][y] + 1;
d.addLast(new int[]{nx, ny});
}
}
return ans;
}
}
5. 总结
「多源 BFS」，通过建立「虚拟源点」，我们可以将其转化回「单源 BFS」问题。
实现上我们只需要将所有的「真实点」进行入队，然后再进行 BFS 即可。
看起来两者区别不大，但其本质是通过源点/汇点转换，应用常规的 Flood Fill 将多次朴素 BFS 转化为一次 BFS，可以有效降低我们算法的时间复杂度。
参考：
