LC.P1036[逃离大迷宫]

方法一:BFS

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
class Solution {
int EDGE = (int) 1e6, MAX;
Set<Long> set = new HashSet<>();
int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
for (int[] b : blocked) set.add(b[0] * (long) 1e6 + b[1]);
int n = blocked.length;
MAX = n * (n - 1) / 2;
return bfs(source, target) && bfs(target, source);
}

private boolean bfs(int[] source, int[] target) {
Set<Long> visited = new HashSet<>();
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(source);
visited.add(source[0] * (long) 1e6 + source[1]);
while (!queue.isEmpty() && visited.size() <= MAX) {
int[] cur = queue.poll();
int x = cur[0], y = cur[1];
if (x == target[0] && y == target[1]) return true; // 到达目标方格
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx < 0 || nx >= EDGE || ny < 0 || ny >= EDGE) continue;
long hash = nx * (long) 1e6 + ny;
if (set.contains(hash)) continue; // 遇到障碍物
if (visited.contains(hash)) continue; // 已经访问过
queue.offer(new int[]{nx, ny});
visited.add(hash);
}
}
return visited.size() > MAX;
}
}
  • 时间复杂度:$O(n^2)$
  • 空间复杂度:$O(n^2)$