一个1000000*1000000的二维平面，中间有一些格子是障碍物（由blocked数组给出），给出起点和终点，问能否通过每步走东南西北中的一个方向一步来到达
直接搜整个平面会TLE，但由题目描述可知最多只有200个障碍物，由Discussion（）得到启发，最多只要搜len(blocked)步长就可以得知起点或者终点有没有被完全阻挡，只要从起点和终点开始各BFS len(blocked)步长即可
1 #1036
2 #Runtime: 2870 ms
3 #Memory Usage: 26.5 MB
4
5 class Solution(object):
6 def BFS(self, source, target):
7 m, n = 1000000, 1000000
8 d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
9 q = deque([[source[0], source[1], 0]])
10 vis = set()
11 vis.add((source[0], source[1]))
12 while q:
13 x, y, stp = q.popleft()
14 if stp > len(self.blocked) or [x, y] == target:
15 return True
16 for dx, dy in d:
17 tx = x + dx
18 ty = y + dy
19 if 0 <= tx < 10**6 and 0 <= ty < 10**6 and (tx, ty) not in vis and (tx, ty) not in self.blocked:
20 vis.add((tx, ty))
21 q.append([tx, ty, stp + 1])
22 return False
23
24 def isEscapePossible(self, blocked, source, target):
25 """
26 :type blocked: List[List[int]]
27 :type source: List[int]
28 :type target: List[int]
29 :rtype: bool
30 """
31 self.blocked = {tuple(p) for p in blocked}
32 return self.BFS(source, target) and self.BFS(target, source)