[LeetCode] Escape a Large Maze

1036. Escape a Large Maze

There is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are (x, y).

We start at the source = [sx, sy] square and want to reach the target = [tx, ty] square. There is also an array of blocked squares, where each blocked[i] = [xi, yi] represents a blocked square with coordinates (xi, yi).

Each move, we can walk one square north, east, south, or west if the square is not in the array of blocked squares. We are also not allowed to walk outside of the grid.

Return true if and only if it is possible to reach the target square from the source square through a sequence of valid moves.

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
class Solution {
long long makeKey(int x, int y) {return (((long long)x)<<32) + y;}
bool bfs(unordered_set<long long>& v, vector<int>& from, vector<int>& to, int block) {
int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
queue<pair<int, int>> q;
q.push({from[0], from[1]});
for(int step = 0; step <= 200 and !q.empty() and q.size() < block; step++) {
int size = q.size();
while(size--) {
auto [x, y] = q.front();
q.pop();
for(int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(0 <= nx && nx < 1000000 && 0 <= ny && ny < 1000000 and v.insert(makeKey(nx, ny)).second) {
if(nx == to[0] and ny == to[1]) return true;
q.push({nx, ny});
}
}
}
}
return !q.empty();
}
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
if(blocked.empty()) return true;
unordered_set<long long> vs, vt;
for(auto& b : blocked) {
vs.insert(makeKey(b[0], b[1]));
vt.insert(makeKey(b[0], b[1]));
}

return bfs(vs, source, target, blocked.size()) && bfs(vt, target, source, blocked.size()) ;
}
};

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/01/PS/LeetCode/escape-a-large-maze/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.