# 1036. Escape a Large Maze

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y).

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.

Constraints:

• 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

0th      _________________________
|O O O O O O O X
|O O O O O O X
|O O O O O X
|O O O O X
.O O O X
.O O X
.O X
200th    |X

class Solution {
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
unordered_set<long> visited;
for (auto &a : blocked) visited.insert(a[0] * 1e6 + a[1]);
return helper(visited, source, target) && helper(visited, target, source);
}
bool helper(unordered_set<long> visited, vector<int>& source, vector<int>& target) {
int N = 1e6, cnt = 0;
vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
queue<vector<int>> q;
q.push(source);
visited.insert((long)source[0] * N + source[1]);
while (!q.empty()) {
auto t = q.front(); q.pop();
if (t == target) return true;
for (auto &dir : dirs) {
int x = t[0] + dir[0], y = t[1] + dir[1];
if (x < 0 || x >= N || y < 0 || y >= N || visited.count((long)x * N + y)) continue;
visited.insert((long)x * N + y);
q.push({x, y});
if (++cnt == 20000) return true;
}
}
return false;
}
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1036

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

https://leetcode.com/problems/escape-a-large-maze/discuss/282860/C%2B%2B-Limited-BFS-28-ms

https://leetcode.com/problems/escape-a-large-maze/discuss/282849/Python-BFS-and-DFS-The-whole-problem-is-broken

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation