题目形容
这是 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 原题链接和其余优选题解。