共计 4097 个字符，预计需要花费 11 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 「1162. 地图分析」，难度为 「中等」。
你当初手里有一份大小为 的 网格，下面的每个 单元格 都用 和 标记好了。
其中 代表陆地，代表海洋，请你找出一个陆地单元格，这个陆地单元格到离它最近的海洋单元格的间隔是最大的。
咱们这里说的间隔是「曼哈顿间隔」：和 这两个单元格之间的间隔是。
如果网格上只有海洋或者陆地，请返回。
示例 1：
输出：[[1,0,1],[0,0,0],[1,0,1]]
输入：2
解释：陆地单元格 (1, 1) 和所有海洋单元格之间的间隔都达到最大，最大间隔为 2。示例 2：
输出：[[1,0,0],[0,0,0],[0,0,0]]
输入：4
解释：陆地单元格 (2, 2) 和所有海洋单元格之间的间隔都达到最大，最大间隔为 4。提醒：
- 1 <= grid.length == grid[0].length <= 100
- grid[i][j] 不是 就是
单源 BFS
通常咱们应用 BFS 求最短路，都是针对如下场景：从特定的终点登程，求解达到特定起点的最短距离。
这是一类非凡的「单源最短路」问题：实质是在一个边权为 的图上，求从特定「源点」登程达到特定「汇点」的最短门路。
对于本题，如果套用「单源最短路」做法，咱们须要对每个「陆地」地位做一次 BFS：求得每个「陆地」的最近海洋间隔，而后在所有的间隔中取 作为答案。
单次 BFS 的最坏状况须要扫描残缺个矩阵，复杂度为。
同时，最多有 个陆地区域须要做 BFS，因而这样的做法复杂度为，并且 可间接取满。
PS. 数据范畴为，实践上是肯定会超时，但本题数据较弱，Java 2021/06/28 可过。
一些细节：为了不便，咱们在应用哈希表记录间隔时，将二维坐标 转化为对应的一维下标 作为 key 进行存储。
代码：
class Solution {
int n;
int[][] grid;
public int maxDistance(int[][] _grid) {
grid = _grid;
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(i, j));
}
}
}
return ans;
}
// 单次 BFS：求解陆地地位 (x,y) 最近的海洋间隔
int bfs(int x, int y) {int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
Deque<int[]> d = new ArrayDeque<>();
Map<Integer, Integer> map = new HashMap<>();
d.addLast(new int[]{x, y});
map.put(x * n + y, 0);
while (!d.isEmpty()) {int[] poll = d.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;
d.addLast(new int[]{nx, ny});
map.put(key, step + 1);
}
}
return -1;
}
}
- 工夫复杂度：
- 空间复杂度：
多源 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;
}
}
- 工夫复杂度：
- 空间复杂度：
总结
明天咱们介绍了「多源 BFS」，通过建设「虚构源点」，咱们能够将其转化回「单源 BFS」问题。
实现上咱们只须要将所有的「实在源点」进行入队，而后再进行 BFS 即可。
看起来两者区别不大，但其本质是通过源点 / 汇点转换，利用惯例的 Flood Fill 将屡次奢侈 BFS 转化为一次 BFS，能够无效升高咱们算法的工夫复杂度。
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1162 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先将所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。