Description
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 <= 200blocked[i].length == 20 <= blocked[i][j] < 10^6source.length == target.length == 20 <= source[i][j], target[i][j] < 10^6source != target
这道题说是有一个一百万乘以一百万大小的格子，有个起始坐标 source 和一个终点坐标 target，还给了一个黑名单 blocked，说是上面的点都不能经过，现在问能否从起点到达终点。首先这道题是一道 Hard 题目，要给予充分的尊重，如果你以为这是简单的迷宫遍历问题的话，那就大错特错了，为啥呢，注意看一下格子的大小，一百万乘以一百万，分分钟让你记录遍历过位置的集合爆栈，这里由于迷宫过于庞大，不一定能直接遍历到终点。其实这道题的解法挺难想的，要从黑名单的长度下手，题目中限定了黑名单的大小不超过 200，那么来思考用 200 个点能多能封闭多大的空间，如下所示：
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
最多能封闭 19900 个点，那么就是说若当前能够遍历到 20000 个点，则说明很大机会可以到达终点。当然极端情况下，终点可能被四个黑名单的上的点犹如围棋围杀般的包围着，所以说还需要反着遍历一般，从终点遍历点，若能在 20000 步内到达，或者达到了 20000 步，都返回 true，否则返回 false。这里可以用 BFS 来做，由于 visited 集合可能会保存 20000 个点，为了提高效率，可以将二维坐标 encode 成为一个数字，这里用横坐标乘以一百万再加上纵坐标，记得要用长整型以免整型溢出。所以这里的 visited 集合可用一个 HashSet，初始时将所有的黑名单 blocked 上的点加进去。然后进行两次 BFS 遍历，分别从起点到终点，和从终点到起点，若两次都返回 true，则整个返回 true，否则返回 false。在 BFS 子函数中，就是经典的 BFS 写法没太大的���别，唯一的不同就是用一个变量 cnt 来记录当前走过的点的个数，当到达了 20000 个，直接返回 true 即可，参见代码如下：
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://leetcode.com/problems/escape-a-large-maze/
https://leetcode.com/problems/escape-a-large-maze/discuss/282860/C%2B%2B-Limited-BFS-28-ms