leetcode 1036 - Escape a Large Maze

https://leetcode.com/problems/escape-a-large-maze/

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.

We start at the source square and want to reach the target square. Each move, we can walk to a 4-directionally adjacent square in the grid that isn’t in the given list of blocked squares.

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

Example 1:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
Explanation:
The target square is inaccessible starting from the source square, because we can’t walk outside the grid.
Example 2:

Input: blocked = [], source = [0,0], target = [999999,999999]
Output: true
Explanation:
Because there are no blocked cells, it’s possible to reach the target square.

Note:

0 <= blocked.length <= 200
blocked[i].length == 2
0 <= blocked[i][j] < 10^6
source.length == target.length == 2
0 <= source[i][j], target[i][j] < 10^6
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
38
39
40
41
42
43
44
class Solution {
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
return bfs(blocked, source, target) && bfs(blocked, target, source);
}

bool bfs(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
unordered_set<long> set_blocked, set_visited;
queue<pair<int,int>> q;

for (auto &v : blocked)
set_blocked.insert(get_index(v[0], v[1]));

q.push({source[0], source[1]});
vector<vector<int>> dirs = {{0,1},{1,0},{0,-1},{-1,0}};
int count = 1;

while (!q.empty()) {
auto p = q.front(); q.pop();

for (auto dir : dirs) {
int x = p.first + dir[0];
int y = p.second + dir[1];

if (x < 0 || x >= 1000000 || y < 0 || y >= 1000000) continue;
if (x == target[0] && y == target[1]) return true;

long index = get_index(x, y);
if (set_blocked.count(index) || set_visited.count(index)) continue;

set_visited.insert(index);
q.push({x,y});

if (count++ == 20000) return true;
}
}

return false;
}

long get_index(int x, int y) {
return x * 1000000UL + y;
}
};