迷宫 II

Submission

运行时间: 59 ms

内存: 16.6 MB

class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        m=len(maze)
        n=len(maze[0])
        dir=[(1,0),(-1,0),(0,1),(0,-1)]
        #visited=[[False]*n for _ in range(m)]
        dis=[[inf]*n for _ in range(m)]
        q=[(0,start[0],start[1])]
        #visited[start[0]][start[1]]=True
        dis[start[0]][start[1]]=0
        while q:
            d,i,j=heapq.heappop(q)
            if d>dis[i][j]:
                continue
            if [i,j]==destination:
                return d
            for dx,dy in dir:
                x,y=i+dx, j+dy
                if 0<=x<m and 0<=y<n:
                    if maze[x][y]==1:
                        continue
                    elif maze[x][y]==0:
                        tmp=0
                        while 0<=x<m and 0<=y<n and maze[x][y]==0:
                            tmp+=1
                            x,y=x+dx,y+dy
                        x,y=x-dx,y-dy
                        if dis[x][y]>dis[i][j]+tmp:
                            dis[x][y]=dis[i][j]+tmp
                            heapq.heappush(q,(dis[x][y],x,y))
                            #visited[x][y]=True
        return -1

Explain

这道题使用 Dijkstra 算法求解最短路径。主要思路是利用优先队列（小根堆）来存储节点，每次从队列中取出距离最小的节点进行扩展，直到找到终点或者所有可达节点都已访问过。在迷宫中，从一个位置可以往四个方向滚动，每个方向滚动到obstacles或边界时停止，计算每一段连续滚动的距离，更新相邻节点的最短距离。

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

空间复杂度: O(mn)

class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        m = len(maze)
        n = len(maze[0])
        dir = [(1,0), (-1,0), (0,1), (0,-1)]  # 四个滚动方向
        dis = [[inf] * n for _ in range(m)]  # 记录每个节点的最短距离
        q = [(0, start[0], start[1])]  # 优先队列，存储 (距离，行坐标，列坐标)
        dis[start[0]][start[1]] = 0  # 起点距离初始化为0
        
        while q:
            d, i, j = heapq.heappop(q)  # 取出距离最小的节点
            if d > dis[i][j]:  # 如果当前距离大于已记录的最短距离，跳过
                continue
            if [i, j] == destination:  # 如果到达终点，返回最短距离
                return d
            
            # 向四个方向扩展
            for dx, dy in dir:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n:
                    if maze[x][y] == 1:  # 如果是障碍物，跳过
                        continue
                    elif maze[x][y] == 0:  # 如果是空地，计算滚动距离
                        tmp = 0
                        while 0 <= x < m and 0 <= y < n and maze[x][y] == 0:
                            tmp += 1
                            x, y = x + dx, y + dy
                        x, y = x - dx, y - dy
                        if dis[x][y] > dis[i][j] + tmp:  # 如果当前距离小于已记录的最短距离，更新最短距离并加入队列
                            dis[x][y] = dis[i][j] + tmp
                            heapq.heappush(q, (dis[x][y], x, y))
        
        return -1  # 如果无法到达终点，返回-1

Explore

Dijkstra算法适用于处理带权重的图中的最短路径问题，其中每个转移的代价可以不同。在迷宫问题中，每次移动可以跨越多个空白单元格，直到遇到边界或障碍，因此每次移动的成本（距离）是变化的。相比之下，BFS仅适用于每步成本相同的情况，而DFS则主要用于遍历或搜索，不专注于找到最短路径。因此，使用Dijkstra算法可以更精确地处理不同移动成本，从而找到真正的最短路径。

是的，在这个迷宫问题的Dijkstra算法实现中，优先队列中的元素优先级是基于每个节点到起点的累计距离。这是因为Dijkstra算法的核心是每次都从已探索的节点中选择一个具有最小累计距离的节点进行扩展，以保证算法的正确性和效率。

这种情况发生是因为同一个节点可能通过不同的路径被多次添加到优先队列中。当从队列中取出一个节点时，如果它的距离大于已记录的最短距离，这意味着我们已经找到了一个更优的路径到达这个节点。继续处理这个较大距离的节点将是无效的，因为它不会导致任何更短的路径。跳过这样的节点可以避免不必要的计算，提高算法效率。

在向外扩展时，代码通过检查每个新坐标是否在迷宫的边界内来处理边界条件。即在每次尝试移动到新位置之前，都会检查新的行坐标和列坐标是否在迷宫的有效范围（0到m-1行和0到n-1列）。如果坐标超出这个范围，就不会继续在该方向移动，从而避免了数组越界的问题。