LeetCode 1036. 逃离大迷宫

题目描述：
在一个 1,000,000 x 1,000,000 的巨大网格中，给你一个 blocked 数组，表示网格中被阻塞的格子坐标（每个坐标是一个长度为 2 的数组，例如 [x, y]）。同时给你一个起点 source 和一个终点 target，它们也都是长度为 2 的数组。你需要判断是否可以从起点移动到终点，移动规则是每次可以向上、下、左、右四个方向之一移动一个格子，但不能移动到被阻塞的格子，也不能移动到网格边界之外（即坐标需满足 0 <= x, y < 1e6）。如果从起点到终点存在一条路径，则返回 true，否则返回 false。blocked 的长度不超过 200。

解题思路：
此题的关键在于网格极大（1e6 x 1e6），但障碍块的数量最多只有 200 个。如果直接进行 BFS/DFS 搜索整个网格，在无障碍时可能遍历巨大空间导致超时。因此需要利用障碍数量的限制条件，从一个更高层次的角度来分析可达性。

核心思路是：

1. 如果起点或终点被障碍包围，则无法到达。但障碍最多 200 个，能包围的最大区域是有限的。
2. 包围区域的最大范围：200 个障碍最多能围住多少个非障碍格子？想象障碍排成一条斜线，能围出的最大区域近似于一个三角形，面积约为 n*(n-1)/2（n 为障碍数）。
3. 因此，我们可以从起点和终点分别进行 BFS/DFS，如果能在访问不超过 MAX_AREA 个格子之前到达目标点（或对方访问过的区域），则可达。
4. 如果从起点和终点出发，都能访问超过 MAX_AREA 个格子仍未相遇，则说明起点和终点都不在封闭区域内，必然可达（因为障碍不能同时围住两个不连通的巨大区域）。

步骤详解：

步骤 1：定义最大包围区域面积
障碍最多 200 个，它们能围成的最大连通非障碍格子数是多少？
思考极端情况：障碍排成一条直线（如对角线），可围住的区域近似为一个等腰直角三角形，其直角边长为 n，面积 ≈ n*(n-1)/2。
本题设置 MAX = 200*199/2 = 19900 是常见选择，实际上略大一些也可保证正确性。我们取 MAX = 20000。

步骤 2：定义辅助函数

• 将障碍存入哈希集合 blockSet 以便 O(1) 判断。
• 方向数组 dirs = [(0,1),(1,0),(0,-1),(-1,0)]。
• 边界判断：坐标在 [0, 1e6) 范围内。

步骤 3：BFS 有限区域搜索函数
函数 bfs(source, target) 从 source 出发，限制最多访问 MAX 个格子，并返回：

1. 是否在访问过程中遇到了 target。
2. 是否在访问过程中遇到了另一个 BFS 访问过的点（用于双向搜索优化）。
3. 是否访问的格子数超过了 MAX（意味着起点未被障碍完全封闭）。

具体 BFS 过程：

• 使用队列和 visited 集合。
• 每一步从当前点向四个方向扩展，如果扩展点是 target 则直接返回 true。
• 如果扩展点合法（在边界内、非障碍、未访问过），则加入队列。
• 当 visited 集合大小超过 MAX 时，停止搜索，返回“未被封闭”的状态。

步骤 4：整体判断逻辑

1. 如果起点或终点本身是障碍，直接返回 false。
2. 从起点 BFS 找终点，如果找到则返回 true。
3. 从终点 BFS 找起点，如果找到则返回 true。
4. 如果从起点出发访问的格子数超过 MAX，并且从终点出发访问的格子数也超过 MAX，说明两个点都不在封闭区域内，必然连通，返回 true。
5. 否则返回 false。

举例说明：
例：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]。

• MAX = 2*1/2 = 1（此处障碍数 n=2）。但实际取 MAX=20000 也适用，因为本题障碍数最大 200，MAX 固定即可。
• 从 [0,0] 出发，可走到 (0,0) 和 (1,0) 等，但 (0,1) 和 (1,0) 是障碍，所以从起点出发访问格子数不会超过 2（实际上只有起点自身和可能的 (1,0) 被阻挡），但 BFS 可尝试其他方向，最终可能访问超过 20000 个格子吗？不会，因为这里只是示意。
  实际上，当起点和终点都不被封闭时，两个 BFS 都会超过 MAX 停止，从而判定为 true。

代码框架（Python）：

from collections import deque

class Solution:
    def isEscapePossible(self, blocked, source, target):
        if not blocked:
            return True
        
        blockSet = set(map(tuple, blocked))
        dirs = [(0,1),(1,0),(0,-1),(-1,0)]
        MAX = 20000  # 根据 n=200 时 n*(n-1)/2 取的安全值
        
        def bfs(source, target, otherVisited=None):
            sx, sy = source
            tx, ty = target
            if (sx, sy) == (tx, ty):
                return True, True
            queue = deque([(sx, sy)])
            visited = set([(sx, sy)])
            while queue:
                x, y = queue.popleft()
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < 10**6 and 0 <= ny < 10**6 and (nx, ny) not in blockSet and (nx, ny) not in visited:
                        if (nx, ny) == (tx, ty):
                            return True, True
                        if otherVisited and (nx, ny) in otherVisited:
                            return True, True
                        visited.add((nx, ny))
                        if len(visited) >= MAX:
                            return False, True  # 未找到，但超出MAX表示未被封闭
                        queue.append((nx, ny))
            return False, False  # 未找到，且被封闭
        
        # 检查起点终点是否直接是障碍
        if tuple(source) in blockSet or tuple(target) in blockSet:
            return False
        
        found1, open1 = bfs(source, target)
        if found1:
            return True
        if open1:  # 起点未被封闭
            found2, open2 = bfs(target, source)
            if found2:
                return True
            if open2:  # 终点未被封闭
                return True
        return False

算法复杂度：

• 每个 BFS 最多访问 MAX+1 个节点，MAX=20000，因此每次 BFS 操作是 O(MAX)。
• 最多两次 BFS，因此总时间复杂度 O(MAX)，空间复杂度 O(MAX)。
• 因为障碍数 ≤ 200，所以 MAX 是常数级，非常高效。

总结：
本题的关键是意识到障碍数量有限时，封闭区域的面积有上限。通过有限步数的 BFS 判断起点和终点是否在封闭区域内，从而避免对整个巨大网格的搜索。这种思路是“有限阻塞搜索”的经典应用。