迷宫 III

Submission

运行时间: 33 ms

内存: 16.3 MB

class Solution:
    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
        # dijkstra算法，并且需要记录路线
        row,col = len(maze),len(maze[0])
        dis = [[inf]*col for i in range(row)]
        dis[ball[0]][ball[1]] = 0
        path = defaultdict(list)
        h = [(0,ball,'')]
        while h:
            d,(i,j),route = heappop(h)
            # 计算终点
            if [i,j] == hole:
                return min(path[(i,j)])
            for dx,dy,way in (1,0,'d'),(-1,0,'u'),(0,1,'r'),(0,-1,'l'):
                x,y = i,j
                while 0<=x<row and 0<=y<col and maze[x][y]==0:
                    x += dx
                    y += dy
                    if [x,y] == hole:
                        break
                else:
                    x -= dx # 撞墙撤回一步
                    y -= dy
                if [x,y] == [i,j]:
                    continue
                nd = abs(x-i) + abs(y-j) + d
                nway = route + way
                if nd < dis[x][y]:
                    dis[x][y] = nd
                    path[(x,y)] = [nway]
                    heappush(h,(nd,(x,y),nway))
                elif nd == dis[x][y]:
                    path[(x,y)].append(nway)
                    heappush(h,(nd,(x,y),nway))

        return 'impossible'

Explain

该题解使用了Dijkstra算法来寻找从起点到终点的最短路径。与普通的Dijkstra算法不同的是，除了记录最短距离外，还需要记录到达每个位置的路线。具体实现时，使用优先队列来存储当前探索到的位置，每次取出距离最小的位置进行扩展。对于每个位置，尝试向四个方向移动，直到撞墙或到达终点。如果到达一个之前未探索过的位置，则更新其距离并记录路线；如果到达一个已探索过的位置，且距离相等，则在该位置的路线中追加新的路线。最后，如果到达终点，则返回字典序最小的路线；如果无法到达终点，则返回'impossible'。

时间复杂度: O(mnlog(mn))

空间复杂度: O(mn(m+n))

class Solution:
    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
        # 迷宫的行数和列数
        row, col = len(maze), len(maze[0])
        # 记录每个位置的最短距离，初始化为无穷大
        dis = [[inf] * col for i in range(row)]
        # 起点的距离为0
        dis[ball[0]][ball[1]] = 0
        # 记录每个位置的路线
        path = defaultdict(list)
        # 优先队列，存储(距离,(x坐标,y坐标),路线)，按距离从小到大排序
        h = [(0, ball, '')]

        while h:
            # 取出距离最小的位置
            d, (i, j), route = heappop(h)
            # 如果到达终点，返回字典序最小的路线
            if [i, j] == hole:
                return min(path[(i, j)])
            # 向四个方向扩展
            for dx, dy, way in (1, 0, 'd'), (-1, 0, 'u'), (0, 1, 'r'), (0, -1, 'l'):
                x, y = i, j
                # 沿当前方向移动，直到撞墙或到达终点
                while 0 <= x < row and 0 <= y < col and maze[x][y] == 0:
                    x += dx
                    y += dy
                    if [x, y] == hole:
                        break
                else:
                    # 撞墙，回退一步
                    x -= dx
                    y -= dy
                # 如果没有移动，则跳过该方向
                if [x, y] == [i, j]:
                    continue
                # 计算到达新位置的距离和路线
                nd = abs(x - i) + abs(y - j) + d
                nway = route + way
                # 如果新距离更短，则更新距离和路线
                if nd < dis[x][y]:
                    dis[x][y] = nd
                    path[(x, y)] = [nway]
                    heappush(h, (nd, (x, y), nway))
                # 如果新距离等于当前最短距离，则追加路线
                elif nd == dis[x][y]:
                    path[(x, y)].append(nway)
                    heappush(h, (nd, (x, y), nway))
        
        # 无法到达终点
        return 'impossible'

Explore

在实现迷宫问题的Dijkstra算法中，处理撞墙的逻辑是通过在移动过程中检查下一个移动的格子是否有效（即是否在迷宫范围内且不是墙）。当沿着某一方向前进且即将移动到的格子是墙时（或者超出迷宫边界），算法会停止在当前方向的前进，并进行回退一步的操作。具体地，在代码中，这一逻辑是通过在循环条件判断中将移动到的下一个位置设为墙或出界前的最后一个合法格子实现的。这意味着一旦发现下一个位置不合法，循环会结束，此时的坐标还是合法的最后位置，但在循环结束后，代码会减去最后一次的移动（dx或dy），使(x, y)回退到最后一个合法的位置。

在Dijkstra算法中，当发现一条到达某个位置的相同长度的新路径时，将这条路径加入到该位置的路径列表中，这种处理方式确实会增加算法的空间复杂度（因为需要存储额外的路径信息）。此外，每次向优先队列中添加相同距离的新路径，也会稍微增加时间复杂度，因为优先队列需要对更多的元素进行排序。然而，这种影响通常是可接受的，因为它使得我们能够探索所有可能的最短路径，进而可以在最后选择字典序最小的路径，这在某些应用场景下是有用的。

是的，存在可能有多条相同长度但字典序不同的最短路径的情况。在这种情况下，题解中通过维护一个路径列表，并在到达终点时从这些路径中选择一个字典序最小的路径来返回。这通过在最终到达终点时，比较存储在路径列表中的所有路径，选择出字典序最小的一个实现。这种方法确保了无论有多少条相同长度的路径，总能返回一个确定且最优的结果。

在Dijkstra算法中，如果一个位置的新计算距离小于已记录的距离，则意味着我们找到了一条更短的路径到达该位置，因此会更新该位置的距离并替换原有的路径。这种操作不会导致遗漏‘优秀’路径，因为所谓的优秀路径应当是指更短的路径。算法的目标是找到从起点到终点的最短路径，因此，只有更短的路径才被考虑为“优秀”，而更长的路径即使在字典序上较好也会被舍弃。这是因为我们的首要目标是最小化路径长度，而非路径的字典序。