本文主要是介绍Leetcode 499. The Maze III [Python]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
BFS, 将每个点到达目标点的步数和路径设置为无限和空。同时设置查验函数，查看每次挪动是否越界或者撞墙。再设置对比检查函数，当一个点通过某些步数可以到达目标点，且从起点到这个点的步数 + 这个点到目标点步数小于上一次某个点可以到达目标点所用的步数；或者步数相同，但是路径字符串更小，则更新可以到达目标点的步数和路径。 BFS的时候，每次弹出位置，开始遍历四个方向，此时需要使用while循环， 在当前方向上走，只要不越界撞墙，就可以继续此方向，而不然就继续换下一个方向。在while循环内，如果可以到达目标点，则检查更新步数和路径到终点上。如果再某个方向上周到了边界或者撞墙，则同样检查更新停止点上的步数和路径。
direct = {'d':(1,0), 'u':(-1,0), 'r':(0,1), 'l':(0,-1) }class Solution:def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:distance = [[(float('inf'),'') for _ in range(len(maze[0]))] for _ in range(len(maze))]distance[ball[0]][ball[1]] = (0,'')que = collections.deque()que.append((ball[0], ball[1]))while que:x,y = que.popleft()for d in direct.keys():dx,dy = direct[d]nx,ny = x,ystep = 0while self.valid(maze, nx + dx, ny + dy):nx += dxny += dystep += 1if nx == hole[0] and ny == hole[1]:self.check(maze, d, step, x, y, nx, ny, distance, que)self.check(maze, d, step, x, y, nx, ny, distance, que)if distance[hole[0]][hole[1]][1] == '':return 'impossible'return distance[hole[0]][hole[1]][1]def valid(self, maze, x, y):if x < 0 or y < 0 or x >= len(maze) or y >= len(maze[0]):return Falsereturn maze[x][y] == 0def check(self, maze, d, step, x, y, nx, ny, distance, que):if distance[x][y][0] + step < distance[nx][ny][0] or (distance[x][y][0] + step == distance[nx][ny][0] and distance[x][y][1] + d < distance[nx][ny][1]):distance[nx][ny] = (distance[x][y][0] + step, distance[x][y][1] + d)que.append((nx,ny))这篇关于Leetcode 499. The Maze III [Python]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
