一個(gè)1000000*1000000的二維平面，中間有一些格子是障礙物（由blocked數(shù)組給出），給出起點(diǎn)和終點(diǎn)，問(wèn)能否通過(guò)每步走東南西北中的一個(gè)方向一步來(lái)到達(dá)
直接搜整個(gè)平面會(huì)TLE，但由題目描述可知最多只有200個(gè)障礙物，由Discussion（）得到啟發(fā)，最多只要搜len(blocked)步長(zhǎng)就可以得知起點(diǎn)或者終點(diǎn)有沒(méi)有被完全阻擋，只要從起點(diǎn)和終點(diǎn)開始各BFS len(blocked)步長(zhǎng)即可
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)