Hard
题目描述
在一个 1 百万 x 1 百万的 XY 平面网格中，每个网格正方形的坐标为 (x, y)。
我们从起点 source = [sx, sy] 开始，想要到达目标 target = [tx, ty]。还有一个阻塞正方形数组 blocked，其中 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的被阻塞的正方形。
每次移动，我们可以向北、东、南、西四个方向走一个正方形，前提是该正方形不在 blocked 数组中。我们也不允许走出网格。
当且仅当可以通过一系列有效的移动从起点方格到达目标方格时，返回 true。
示例 1：
输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：无法从起点到达目标，因为我们无法移动。
我们不能向北或向东移动，因为那些正方形被阻塞了。
我们不能向南或向西移动，因为我们不能走出网格。
示例 2：
输入：blocked = [], source = [0,0], target = [999999,999999]
输出：true
解释：因为没有被阻塞的格子，所以可以到达目标正方形。
约束条件：
- 0 <= blocked.length <= 200
- blocked[i].length == 2
- 0 <= xi, yi < 10^6
- source.length == target.length == 2
- 0 <= sx, sy, tx, ty < 10^6
- source != target
- 保证 source 和 target 不被阻塞
解题思路
这是一个在巨大网格中的路径搜索问题，关键洞察是：如果被阻塞点形成了包围圈，那么最多只能围困有限个格子。
核心思路
阻塞上限分析：最多200个阻塞点，理论上能形成的最大包围区域是当阻塞点排成直角三角形时，最多包围约 200×199/2 ≈ 20000 个格子。
双向BFS策略：
- 从起点开始BFS，如果能访问超过20000个格子，说明起点没被围困
- 从终点开始BFS，如果能访问超过20000个格子，说明终点没被围困
- 如果两个BFS都没被围困，或者其中一个BFS找到了对方，则返回true
优化技巧：
- 使用set快速判断格子是否被阻塞
- BFS时记录访问过的格子数量，超过阈值就提前退出
- 双向搜索可以减少搜索空间
算法步骤
- 将阻塞点转换为set以便快速查找
- 定义BFS函数，返回是否能访问足够多格子或找到目标
- 分别从起点和终点开始BFS
- 如果两次BFS都成功（没被围困或找到对方），返回true
这种方法巧妙地避免了在巨大网格上进行完整路径搜索的性能问题。
代码实现
class Solution {
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
if (blocked.empty()) return true;
set<pair<int, int>> blockSet;
for (auto& block : blocked) {
blockSet.insert({block[0], block[1]});
}
// 最大可能的围困区域大小
int maxBlocked = blocked.size() * (blocked.size() - 1) / 2;
return bfs(blockSet, source, target, maxBlocked) &&
bfs(blockSet, target, source, maxBlocked);
}
private:
bool bfs(set<pair<int, int>>& blockSet, vector<int>& start, vector<int>& end, int maxBlocked) {
queue<pair<int, int>> q;
set<pair<int, int>> visited;
q.push({start[0], start[1]});
visited.insert({start[0], start[1]});
vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while (!q.empty() && visited.size() <= maxBlocked) {
auto [x, y] = q.front();
q.pop();
// 找到目标
if (x == end[0] && y == end[1]) {
return true;
}
for (auto& dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
// 检查边界和阻塞
if (nx < 0 || nx >= 1000000 || ny < 0 || ny >= 1000000 ||
blockSet.count({nx, ny}) || visited.count({nx, ny})) {
continue;
}
q.push({nx, ny});
visited.insert({nx, ny});
}
}
// 如果访问的格子数超过最大围困数，说明没被围困
return visited.size() > maxBlocked;
}
};
class Solution:
def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
if not blocked:
return True
block_set = set(map(tuple, blocked))
max_blocked = len(blocked) * (len(blocked) - 1) // 2
def bfs(start, end):
queue = deque([start])
visited = {tuple(start)}
while queue and len(visited) <= max_blocked:
x, y = queue.popleft()
if [x, y] == end:
return True
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nx, ny = x + dx, y + dy
if (0 <= nx < 1000000 and 0 <= ny < 1000000 and
(nx, ny) not in block_set and (nx, ny) not in visited):
queue.append([nx, ny])
visited.add((nx, ny))
return len(visited) > max_blocked
return bfs(source, target) and bfs(target, source)
public class Solution {
public bool IsEscapePossible(int[][] blocked, int[] source, int[] target) {
if (blocked.Length == 0) return true;
HashSet<(int, int)> blockSet = new HashSet<(int, int)>();
foreach (var block in blocked) {
blockSet.Add((block[0], block[1]));
}
int maxBlocked = blocked.Length * (blocked.Length - 1) / 2;
return BFS(blockSet, source, target, maxBlocked) &&
BFS(blockSet, target, source, maxBlocked);
}
private bool BFS(HashSet<(int, int)> blockSet, int[] start, int[] end, int maxBlocked) {
Queue<(int, int)> queue = new Queue<(int, int)>();
HashSet<(int, int)> visited = new HashSet<(int, int)>();
queue.Enqueue((start[0], start[1]));
visited.Add((start[0], start[1]));
int[][] dirs = new int[][] { new int[] {0, 1}, new int[] {0, -1}, new int[] {1, 0}, new int[] {-1, 0} };
while (queue.Count > 0 && visited.Count <= maxBlocked) {
var (x, y) = queue.Dequeue();
if (x == end[0] && y == end[1]) {
return true;
}
foreach (var dir in dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx < 0 || nx >= 1000000 || ny < 0 || ny >= 1000000 ||
blockSet.Contains((nx, ny)) || visited.Contains((nx, ny))) {
continue;
}
queue.Enqueue((nx, ny));
visited.Add((nx, ny));
}
}
return visited.Count > maxBlocked;
}
}
var isEscapePossible = function(blocked, source, target) {
if (blocked.length === 0) return true;
const blockedSet = new Set(blocked.map(b => b[0] + ',' + b[1]));
const maxArea = blocked.length * (blocked.length - 1) / 2;
const bfs = (start, end) => {
const visited = new Set();
const queue = [start];
visited.add(start[0] + ',' + start[1]);
const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
while (queue.length > 0) {
const [x, y] = queue.shift();
if (x === end[0] && y === end[1]) return true;
if (visited.size > maxArea) return true;
for (const [dx, dy] of dirs) {
const nx = x + dx;
const ny = y + dy;
const key = nx + ',' + ny;
if (nx >= 0 && nx < 1000000 && ny >= 0 && ny < 1000000 &&
!blockedSet.has(key) && !visited.has(key)) {
visited.add(key);
queue.push([nx, ny]);
}
}
}
return false;
};
return bfs(source, target) && bfs(target, source);
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n²) - 其中 n 是阻塞点数量，最坏情况下需要访问 n(n-1)/2 个格子 |
| 空间复杂度 | O(n²) - 存储阻塞点集合和访问过的格子，最多 O(n²) 个格子 |