题目描述
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
题意:在一个 10^6 x 10^6
的网格中,每个网格块的坐标为(x, y)
,其中 0 <= x, y < 10^6
。
我们从源方格source
开始出发,意图赶往目标方格target
。每次移动,我们都可以走到网格中在四个方向上相邻的方格,只要该方格不在给出的封锁列表blocked
上。
只有在可以通过一系列的移动到达目标方格时才返回 true。否则,返回 false。
算法1
(有限BFS)
首先这一题肯定不能直接使用暴力搜索,因为格子的长度为10^6。这里我们观察到一个很重要的一点,就是障碍点的个数不超过200。那么我们可以考虑如何使用这200个障碍点才能让起点和终点走不到呢?除非某一个点被障碍点和墙围起来了。那么最多能够围多少个格子呢?我们将200放在正方形一个角上,那么这个等边直角三角形的格子数为200。这也就意味着如果我们从某一个点为起点进行BFS,如果能够访问超过200个点,那么这个点就没有被围起来。
根据上述分析,我们可以起点为起点进行BFS,如果能够搜索到终点或者遍历到200个点以上,我们返回true,再以终点为起点进行BFS,如果能够搜索到终点或者遍历到200个点以上,我们返回true。
如果上面两次搜索都返回true,那么说明我们可以从起点到达终点。我们使用long long为每一个节点进行编号,使用哈希表记录哪些节点被BFS过了。
class Solution {
public:
typedef long long LL;
long long N = 1000000;
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
bool check(vector<int>& source,unordered_set<LL>& blocks,LL target)
{
unordered_set<LL> visit;
queue<LL> q;
q.push(source[0] * N + source[1]);
visit.insert(q.front());
while(!q.empty())
{
LL p = q.front();
q.pop();
LL r = p / N,c = p % N;
for(int i = 0 ; i < 4 ; i ++)
{
LL x = r + dx[i], y = c + dy[i];
LL idx = N * x + y;
if(x >= 0 && x < N && y >= 0 && y < N && visit.count(idx) == 0 && blocks.count(idx) == 0)
{
if(idx == target || q.size() > 200) return true;
visit.insert(idx);
q.push(idx);
}
}
}
return false;
}
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
unordered_set<LL> blocks;
for(auto &p : blocked)
blocks.insert(p[0] * N + p[1]);
return check(source,blocks,target[0] * N + target[1]) && check(target,blocks,source[0] * N + source[1]);
}
};