0 <= blocked.length <= 200
blocked[i].length == 2
0 <= xi, yi < 106
source.length == target.length == 2
0 <= sx, sy, tx, ty < 106
source != target
题目数据保证 source 和 target 不在封锁列表内
class Solution { public: bool isEscapePossible(vector<vector<int>>& blocked,
vector<int>& source, vector<int>& target) { int size = blocked.size(),
maxPoints = size * (size - 1) / 2; // size个障碍物最多可以围住maxPoints个点 if (size < 2) {
return true; // 少于两个block，是不可能围住一个点的 } unordered_set<long long> blockedPoints;
getBlockedPoints(blocked, blockedPoints); return BFS(source, target, maxPoints,
blockedPoints) && BFS(target, source, maxPoints, blockedPoints); } void
getBlockedPoints(vector<vector<int>>& blocked, unordered_set<long long>&
blockedPoints) { for (auto& point : blocked) { blockedPoints.insert(((long
long)point[0] << 32) | point[1]); } } bool BFS(vector<int>& source,
vector<int>& target, int maxPoints, unordered_set<long long>& blockedPoints) {
int count = 1; long long size = 1000000, dr[4] = { 0,1,0,-1 }, dc[4] = {
1,0,-1,0 }; long long sourcePoint = ((long long)source[0] << 32) | source[1],
targetPoint = ((long long)target[0] << 32) | target[1]; queue<long long>
points; unordered_set<long long> visited; points.push(sourcePoint);
visited.insert(sourcePoint); while (!points.empty()) { long long r =
points.front() >> 32, c = points.front() & 0xffffffff; points.pop(); for (int i
= 0; i < 4; ++i) { long long nr = r + dr[i], nc = c + dc[i]; if (nr < 0 || nr
>= size || nc < 0 || nc >= size) { continue; } long long npoint = (nr << 32) |
nc; if (npoint == targetPoint) { return true; } if (visited.count(npoint) == 0
&& blockedPoints.count(npoint) == 0) { if (++count > maxPoints) { return true;
} points.push(npoint); visited.insert(npoint); } } } return false; } };

GitHub

Gitee