逃离大迷宫

难度: Hard

在一个 10⁶ x 10⁶ 的网格中，每个网格上方格的坐标为 (x, y) 。

现在从源方格 source = [s_x, s_y] 开始出发，意图赶往目标方格 target = [t_x, t_y] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [x_i, y_i] 表示坐标为 (x_i, y_i) 的方格是禁止通行的。

每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表 blocked 上。同时，不允许走出网格。

只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。

示例 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 <= x_i, y_i < 10⁶
source.length == target.length == 2
0 <= s_x, s_y, t_x, t_y < 10⁶
source != target
题目数据保证 source 和 target 不在封锁列表内

Submission

运行时间: 113 ms

内存: 23.8 MB

class Solution:
    def isEscapePossible(
        self, blocked: List[List[int]], source: List[int], target: List[int]
    ) -> bool:
        n = 1000000
        limit = len(blocked) * (len(blocked) - 1) / 2

        def dfs(x, y, tx, ty, visited):
            nonlocal cnt
            if cnt >= limit:
                return True
            if x == tx and y == ty:
                return True
            visited.add(x * n + y)
            cnt += 1
            if (
                x + 1 < n
                and (x + 1) * n + y not in visited
                and dfs(x + 1, y, tx, ty, visited)
            ):
                return True
            if (
                x - 1 >= 0
                and (x - 1) * n + y not in visited
                and dfs(x - 1, y, tx, ty, visited)
            ):
                return True
            if (
                y - 1 >= 0
                and x * n + y - 1 not in visited
                and dfs(x, y - 1, tx, ty, visited)
            ):
                return True
            if (
                y + 1 < n
                and x * n + y + 1 not in visited
                and dfs(x, y + 1, tx, ty, visited)
            ):
                return True
            return False

        cnt = 0
        visited = set()
        for x, y in blocked:
            visited.add(x * n + y)
        if not dfs(source[0], source[1], target[0], target[1], visited):
            return False

        cnt = 0
        visited = set()
        for x, y in blocked:
            visited.add(x * n + y)
        if not dfs(target[0], target[1], source[0], source[1], visited):
            return False
        return True

Explain

该题解采用了深度优先搜索（DFS）来检查从源点到目标点是否存在一条路径。关键在于处理大量的封锁点，为此，题解中使用了一个计算技巧：基于最坏情况下被封锁的最大区域的大小来设置一个探索限制。当被阻塞的点数量为b时，最坏情况下它们可以封锁的区域为 b*(b-1)/2，即在这个范围内搜索。如果在达到这个区域限制之前就找到了目标点，或者探索的区域达到了这个限制，就认为存在路径。如果在达到限制前未找到路径，则假定被封锁。题解首先从源点开始，尝试到达目标点；然后反过来，从目标点尝试到达源点，两者都必须是可行的，才能最终返回 true。

时间复杂度: O(b^2)

空间复杂度: O(b^2)

class Solution:
    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
        n = 1000000
        limit = len(blocked) * (len(blocked) - 1) / 2

        def dfs(x, y, tx, ty, visited):
            nonlocal cnt
            if cnt >= limit:
                return True
            if x == tx and y == ty:
                return True
            visited.add(x * n + y)
            cnt += 1
            if (x + 1 < n and (x + 1) * n + y not in visited and dfs(x + 1, y, tx, ty, visited)):
                return True
            if (x - 1 >= 0 and (x - 1) * n + y not in visited and dfs(x - 1, y, tx, ty, visited)):
                return True
            if (y - 1 >= 0 and x * n + y - 1 not in visited and dfs(x, y - 1, tx, ty, visited)):
                return True
            if (y + 1 < n and x * n + y + 1 not in visited and dfs(x, y + 1, tx, ty, visited)):
                return True
            return False

        cnt = 0
        visited = set()
        for x, y in blocked:
            visited.add(x * n + y)
        if not dfs(source[0], source[1], target[0], target[1], visited):
            return False

        cnt = 0
        visited = set()
        for x, y in blocked:
            visited.add(x * n + y)
        if not dfs(target[0], target[1], source[0], source[1], visited):
            return False
        return True

Explore

这个计算公式基于组合数学中的排列组合概念。假设有b个封锁点，最坏情况下，每个封锁点都能与其他封锁点相连形成一个封闭区域。这可以被视为在b个点中任意选择两个点来形成一条边的场景，其可能的边数是组合数C(b,2)，即b*(b-1)/2。这代表如果b个点完全连接，可以最多形成b*(b-1)/2条边。在几何上，这可以视为b个点最多能围成的凸多边形的边数，尽管实际的封锁区域可能形状各异，但这提供了一个理论上的最大可能封锁区域估计。

在一些情况下，单向搜索可能遇到偏差。例如，从源点到目标点可能存在一条通路，但那条路可能是因为搜索算法的特定路径选择而找到的，而实际上从目标点回到源点可能完全不可行。执行双向搜索可以验证路径的双向可达性，确保无论从哪个方向开始，路径都是开放且可行的，从而增加算法对于路径存在的确认的准确性。

设置探索限制是为了避免在大迷宫中进行过度深入无限的搜索，从而减少计算资源的消耗和提高算法效率。这个限制基于最坏情况下的封锁区域大小，是一种启发式的方法。当搜索达到这个限制时，并没有找到目标点，可以合理地推测路径被封锁。然而，这种方法可能会导致误判，特别是在封锁点分布不均或实际可通过的路径非常复杂时。这种情况下，可能存在通路但未被发现，因为搜索被提前终止了。相反，如果实际封锁点较少，这种方法可能较为保守地认为路径存在。