2022/01/11 - 1036. 逃离大迷宫
1036. 逃离大迷宫 - Hard
Description
1036. 逃离大迷宫
在一个 10^6 x 10^6 的网格中，每个网格上方格的坐标为 (x, y) 。
现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。
每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 blocked 上。同时，不允许走出网格。
只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。
Solutions
看到这道题的时候，我首先就想到了路径搜索类似的问题，所以 DFS 和 BFS 两种方法首先出现在了我的脑子里。这里我就说明一下DFS，BFS的思路和DFS差不多，稍微有一点变化。
如果想看BFS的解法，请看三叶姐的题解：【宫水三叶】BFS + 给定障碍物所能围成的最大面积
TLE，因为坐标系范围太大了如果用DFS的话，非常费时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | class Solution {
Set<String> set = new HashSet<>();
int maxX = 1000000;
int maxY = 1000000;
int[][] directions = new int[][] {
{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
int n = blocked.length;
if (n == 0) return true;
for (int[] b : blocked) {
set.add("[" + b[0] + "," + b[1] + "]");
}
return dfs(source, target);
}
private boolean dfs(int[] source, int[] target) {
if (source[0] == target[0] && source[1] == target[1]) return true;
set.add("[" + source[0] + "," + source[1] + "]");
for (int[] d : directions) {
int newX = source[0] + d[0];
int newY = source[1] + d[1];
if (newX >= 0 && newX <= maxX && newY >= 0 && newY <= maxY && !set.contains(newX + newY)) {
if (dfs(new int[] {newX, newY}, target)) return true;
}
}
return false;
}
}
|
既然上面的DFS解法会TLE，那么就想怎么才能避免这种情况，这时我就只能看看题解了。
大致的思路就是，blocked的长度是有限的，那么假设blocked的长度是len，那么它能围成的最大范围就是len * len，那这样我们就可以记录步数来判断source或者target有没有被围住了，假设步数为step，那么当step > len * len时，就说明是没有被围住，就可以直接返回true了，我们需要分别判断source和target。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | class Solution {
Set<Integer> blo = new HashSet<>();
Set<Integer> vis = new HashSet<>();
int EDGE = (int) 1e6;
int BASE = 131;
int limit = 0;
int[][] directions = new int[][] {
{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
int n = blocked.length;
if (n == 0) return true;
limit = blocked.length * blocked.length;
for (int[] b : blocked) {
blo.add(b[0] * BASE + b[1]);
}
boolean res1 = dfs(source, target, 0);
vis.clear();
boolean res2 = dfs(target, source, 0);
return res1 && res2;
}
private boolean dfs(int[] source, int[] target, int step) {
if (source[0] == target[0] && source[1] == target[1]) return true;
if (step >= limit) return true;
vis.add(source[0] * BASE + source[1]);
for (int[] d : directions) {
int newX = source[0] + d[0];
int newY = source[1] + d[1];
if (newX < 0 || newX >= EDGE || newY < 0 || newY >= EDGE) continue;
if (blo.contains(newX * BASE + newY)) continue;
if (vis.contains(newX * BASE + newY)) continue;
if (dfs(new int[] {newX, newY}, target, step + 1)) return true;
}
return false;
}
}
|