1036. 逃离大迷宫

Difficulty
Hard
Tags
BFS
URL
https://leetcode.cn/problems/escape-a-large-maze/
Star
在一个 10**6 x 10**6 的网格中，每个网格上方格的坐标为 (x, y) 。
现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。
每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 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 <= xi, yi < 106
  • source.length == target.length == 2
  • 0 <= sx, sy, tx, ty < 106
  • source != target
  • 题目数据保证 source 和 target 不在封锁列表内

法1 BFS

思路
因为blocked的大小只有不到200，而棋盘大小相对于200几乎是无限大，遍历光棋盘必然会超时。
一看，block的数量最大只有 200，因此该题的突破口一定是这里。
考虑，起点到终点无法互相到达的情况。
起点，起点被block围住。 终点，终点被block围住。 问题现在转化为 200200 个 block，最多可以围住格子？
notion imagenotion image
显然，同等blocked的数目下，方案二比方案一能围住更多的区域。
因此，可以分别从起点和终点BFS，判断是否被围住，最多遍历 (block)*(block-1)/2(block)∗(block−1)/2 个格子。
如果BFS过程中，找到终点，那么可以到达。 如果BFS过程中，没有找到终点，遍历了超过 (block)*(block-1)/2(block)∗(block−1)/2 个格子，那么说明没有被围住，那么可以到达。 如果不是以上两种情况，即无法到达。
题解
class Solution:
    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
        self.blocked = set([tuple(b) for b in blocked])
        self.max_area = len(blocked) * (len(blocked)-1) // 2

        return self.dfs(source, target) and self.dfs(target, source)
    
    def dfs(self, source, target):
        queue = deque()
        queue.append(source)
        visited = set()
        visited.add(tuple(source))
        edge = 10 ** 6
        while queue:
            cur_loc = queue.popleft()
            for d in [[-1, 0], [0, 1], [0, -1], [1, 0]]:
                nxt_loc = [cur_loc[0] + d[0], cur_loc[1] + d[1]]
                if nxt_loc[0] < 0 or nxt_loc[0] > edge or nxt_loc[1] < 0 or nxt_loc[1] >= edge:
                    continue

                if nxt_loc[0] == target[0] and nxt_loc[1]==target[1]:
                    return True
                
                if tuple(nxt_loc) in visited:
                    continue

                if tuple(nxt_loc) in self.blocked:
                    continue

                visited.add(tuple(nxt_loc))
                queue.append(nxt_loc)

            if len(visited) > self.max_area:
                return True

        return False