788 · 迷宫II - LintCode
在迷宫中有一个球，里面有空的空间和墙壁。球可以通过滚上，下，左或右移动，但它不会停止滚动直到撞到墙上。当球停止时，它可以选择下一个方向。
给定球的起始位置，目标和迷宫，找到最短距离的球在终点停留。距离是由球从起始位置(被排除)到目的地(包括)所走过的空空间的数量来定义的。如果球不能停在目的地，返回-1。
迷宫由二维数组表示。1表示墙和0表示空的空间。你可以假设迷宫的边界都是墙。开始和目标坐标用行和列索引表示。
1.在迷宫中只有一个球和一个目的地。
2.球和目的地都存在于一个空的空间中，它们最初不会处于相同的位置。
3.给定的迷宫不包含边框(比如图片中的红色矩形)，但是你可以假设迷宫的边界都是墙。
4.迷宫中至少有2个空的空间，迷宫的宽度和高度都不会超过100。
Example 1: Input: (rowStart, colStart) = (0,4) (rowDest, colDest)= (4,4) 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 Output: 12 Explanation: (0,4)->(0,3)->(1,3)->(1,2)->(1,1)->(1,0)->(2,0)->(2,1)->(2,2)->(3,2)->(4,2)->(4,3)->(4,4) Example 2: Input: (rowStart, colStart) = (0,4) (rowDest, colDest)= (0,0) 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 Output: 6 Explanation: (0,4)->(0,3)->(1,3)->(1,2)->(1,1)->(1,0)->(0,0)
BFS + 优先队列 = Dijkstra
和上一题的不同之处在于：本题目要求走的距离。
上一题中采用visited数组存放走过的点，因为走过一遍的就不用再走一遍了。但此题不同，即使走过一遍了，如果第二次走时所用步数比第一次少，那么第二次还得走，所以本题用visited数组存放从起点到当前位置所走的距离。
此外，每次从队列中取元素时，该元素都应当为对列里面的元素到终点的最短距离，不然取出来一个正好是终点，但是又不是最短距离，那么就会出错。所以从队列中取元素时，应该按照从开始到该元素的距离排个序，所以，队列中存储的不应该只有节点位置，还应该对应存储开始到当前节点位置的距离，这样才开排序。
题解
class Solution: """ @param maze: the maze @param start: the start @param destination: the destination @return: the shortest distance for the ball to stop at the destination """ def shortestDistance(self, maze, start, destination): ''' distance[x][y] 存放是是从起点到位置[x][y]的路径长度，即距离。 与之前的visited不同的是，之前visited只可以走一次，而distance是可以多次走的， 如果当前距离比之前的距离要小，那么可以放入队列 队列中除了存放坐标外，还存放的从起点到当前坐标的距离， 每次从从队列选一个候选人，都对距离继续一个排序，然后再出队列，这样保证距离小的先扩散查找 ''' distance = [[float('inf')]*len(maze[0]) for _ in range(len(maze))] distance[start[0]][start[1]] = 0 dirs = [[1, 0], [-1, 0], [0, -1], [0, 1]] queue = [] # [x, y, 从起点到当前位置的距离] queue.append([start[0], start[1], 0]) # 队列里面存放这个距离只是为了排序 while queue: queue.sort(key=lambda x:x[2]) # 按照距离升序排放 cur = queue.pop(0) if cur[0:2] == destination: return cur[2] for dir in dirs: x = cur[0] y = cur[1] count = 0 while 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0: x += dir[0] y += dir[1] count += 1 # 撞到墙 或者 边界了。 需要退回去一步 x -= dir[0] y -= dir[1] count -= 1 # 如果到[x][y] 的距离比之气的方式小，那么可以更新距离并且把当下位置存入队列 if distance[cur[0]][cur[1]] + count < distance[x][y]: distance[x][y] = distance[cur[0]][cur[1]] + count queue.append([x, y, distance[x][y]]) return -1
法2 DFS
思路
遍历所有可能，取最短路径。会超时
题解
class Solution: """ @param maze: the maze @param start: the start @param destination: the destination @return: the shortest distance for the ball to stop at the destination """ def shortestDistance(self, maze, start, destination): self.m, self.n = len(maze), len(maze[0]) self.paths = [] visited = set([(start[0], start[1])]) self.dfs(maze, start, destination, 0, visited) if len(self.paths) == 0: return -1 return min(self.paths) def dfs(self, maze, start, destination, step, visited): if start[0] == destination[0] and start[1] == destination[1]: self.paths.append(step) return for move in [(0, 1), (0, -1), (1, 0), (-1, 0)]: x, y = start[0], start[1] # for each move need to reset the step starting_step = step while (x >= 0 and x < self.m and y >= 0 and y < self.n and maze[x][y] != 1): x += move[0] y += move[1] starting_step += 1 x -= move[0] y -= move[1] starting_step -= 1 if (x, y) not in visited: visited.add((x, y)) self.dfs(maze, [x, y], destination, starting_step, visited) visited.remove((x, y))