給定一個(gè)迷宮圖，'.'表示可以走的格子，'+'表示墻，entrance表示初始位置問(wèn)最少多少步可以走出迷宮（出口==位于四壁的'.'且不等于entrance的格子），簡(jiǎn)單BFS，走過(guò)的地方可以用vis記錄，或者把走過(guò)的格子改為+，不再走第二遍
1 #1926
2 #Runtime: 630 ms
3 #Memory Usage: 15.4 MB
4
5 class Solution(object):
6 def nearestExit(self, maze, entrance):
7 """
8 :type maze: List[List[str]]
9 :type entrance: List[int]
10 :rtype: int
11 """
12 m, n = len(maze), len(maze[0])
13 d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
14 q = deque([[entrance[0], entrance[1], 0]])
15 maze[entrance[0]][entrance[1]] = '+'
16 while q:
17 x, y, stp = q.popleft()
18 if stp and (x == 0 or y == 0 or x == m - 1 or y == n - 1):
19 return stp
20 for dx, dy in d:
21 tx = x + dx
22 ty = y + dy
23 if 0 <= tx < m and 0 <= ty < n and maze[tx][ty]=='.':
24 maze[tx][ty] = '+'
25 q.append([tx, ty, stp + 1])
26 return -1