题目描述

在一个 106 x 106 的网格中，每个网格上方格的坐标为 (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 不在封锁列表内

题解思路

如果我们从 开始的点 和 结束的点 分别进行遍历 如果遍历的点都可以超过Max个点 那说明两者是互相连通的

即可以从开始到结束

但是如何定义这个Max点呢

在给定障碍物的情况下 如何利用已有的障碍物得到最大的封锁面积

我们可以利用边界 及障碍物的个数 即可得到最大的封锁面积 也即 len（blocked）* （len（blocked）-1）//2 为Max 点

如果我们从开始到结束 从结束到开始 各进行一次遍历 都可以超过这个点 那么我们就可以互相连通

题解代码

Bound=int(1e6)
class Solution:def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:blocked,max={tuple(p) for p in blocked},len(blocked)*(len(blocked)-1)//2def bfs(start,end):#定义点的数组，当前遍历的点的索引，已经遍历过的点points,ind,visit=[start],0,{tuple(start)}#当未遍历完所有的点while ind<len(points):for dx,dy in (-1,0),(1,0),(0,1),(0,-1):nx,ny=points[ind][0]+dx,points[ind][1]+dyif 0<=nx<Bound and 0<=ny<Bound and (nx,ny) not in visit and (nx,ny) not in blocked:if [nx,ny]==end:return Truevisit.add((nx,ny))points.append((nx,ny))if len(points)>max:return Trueind+=1return Falsereturn bfs(source,target) and bfs(target,source)