Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定一个迷宫图,'.'表示可以走的格子,'+'表示墙,entrance表示初始位置问最少多少步可以走出迷宫(出口==位于四壁的'.'且不等于entrance的格子),简单BFS,走过的地方可以用vis记录,或者把走过的格子改为+,不再走第二遍

 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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理