求0-1矩阵从左上角到右下角只走0的话最快几步到达（可以8个方向行走），BFS
1 #1091
2 #Runtime: 528 ms (Beats 59.73%)
3 #Memory: 13.8 MB (Beats 71.4%)
4
5 class Solution(object):
6 def shortestPathBinaryMatrix(self, grid):
7 """
8 :type grid: List[List[int]]
9 :rtype: int
10 """
11 if grid[0][0] != 0:
12 return -1
13 if len(grid) == 1 and len(grid[0]) == 1:
14 return 1
15 q = deque([(0, 0, 1)])
16 grid[0][0] = 1
17 d = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]
18 while q:
19 x, y, stp = q.popleft()
20 for i in range(8):
21 tx = x + d[i][0]
22 ty = y + d[i][1]
23 if 0 <= tx < len(grid) and 0<= ty < len(grid[0]) and grid[tx][ty] == 0:
24 if tx == len(grid) - 1 and ty == len(grid[0]) - 1:
25 return stp + 1
26 grid[tx][ty] = 1
27 q.append((tx, ty, stp + 1))
28 return -1