Python新手求指导：如何解决2D迷宫最短路径时间计算问题

问题分析 #

这是典型的带权网格最短路径问题——每个格子的通行成本（时间）不一样，普通的广度优先搜索（BFS）只适用于权重相同的场景，所以这里需要用Dijkstra算法来处理，它能高效找到加权图中的最短路径。

核心思路 #

1. 先扫描网格，定位起点S的位置，同时确认终点M是否存在（没有的话直接判定失败）；
2. 用一个距离矩阵记录到达每个格子的最短时间，初始值设为无穷大，起点的时间设为0；
3. 使用优先队列（小顶堆）来每次取出当前耗时最少的位置，向上下左右四个方向扩展；
4. 计算每个相邻格子的通行时间：根据格子类型对应不同耗时，若新路径的时间比已记录的更短，就更新距离并加入队列；
5. 找到终点M后，对比最短时间和给定的Ss，输出对应结果；如果遍历完所有可达位置都没找到M，也判定失败。

Python代码实现 #

import heapq

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    
    # 定义每个格子的耗时映射
    cost_map = {
        'S': 0,  # 起点不需要耗时
        '.': 1,
        '#': 3,
        'Y':5, 'U':5, 'L':5, 'R':5, 'E':5,
        'D':8, 'V':8, 'C':8,
        'M':0   # 终点到达即停止，不需要额外耗时
    }
    
    directions = [(-1,0), (1,0), (0,-1), (0,1)]  # 上下左右
    
    for _ in range(n):
        r = int(input[ptr])
        c = int(input[ptr+1])
        Ss = int(input[ptr+2])
        ptr +=3
        
        grid = []
        start = None
        has_m = False
        for i in range(r):
            row = input[ptr]
            ptr +=1
            grid.append(row)
            if 'S' in row:
                start = (i, row.index('S'))
            if 'M' in row:
                has_m = True
        
        # 如果没有牛奶，直接输出失败
        if not has_m:
            print("Spidey's having marital problems.")
            continue
        
        # 初始化距离矩阵
        INF = float('inf')
        dist = [[INF]*c for _ in range(r)]
        sx, sy = start
        dist[sx][sy] = 0
        
        # 优先队列：(当前时间, x, y)
        heap = []
        heapq.heappush(heap, (0, sx, sy))
        
        found = False
        min_time = INF
        
        while heap:
            current_time, x, y = heapq.heappop(heap)
            
            # 如果当前是终点，记录时间并退出
            if grid[x][y] == 'M':
                min_time = current_time
                found = True
                break
            
            # 如果当前路径的时间比已记录的长，跳过（因为已经有更优路径）
            if current_time > dist[x][y]:
                continue
            
            # 遍历四个方向
            for dx, dy in directions:
                nx = x + dx
                ny = y + dy
                # 检查是否在网格范围内
                if 0 <= nx < r and 0 <= ny < c:
                    # 计算到达该格子的总时间
                    add_time = cost_map[grid[nx][ny]]
                    new_time = current_time + add_time
                    # 如果新时间更短，更新距离并加入堆
                    if new_time < dist[nx][ny]:
                        dist[nx][ny] = new_time
                        heapq.heappush(heap, (new_time, nx, ny))
        
        # 判断结果
        if found and min_time < Ss:
            print(f"Everything's peachy, Spidey escaped in {min_time} seconds.")
        else:
            print("Spidey's having marital problems.")

if __name__ == "__main__":
    main()

代码关键点说明 #

1. 输入处理：用sys.stdin.read()一次性读取所有输入，避免多次IO操作，适合竞赛场景；
2. 耗时映射表：把每个格子类型对应的时间存在字典里，方便快速查找；
3. 优先队列：用heapq模块实现小顶堆，保证每次取出的都是当前耗时最少的位置，这是Dijkstra算法的核心；
4. 距离矩阵：用来剪枝，如果当前路径到某个格子的时间比已经记录的最短时间长，就跳过这个路径，避免无效计算；
5. 边界检查：每次移动前确认新位置在网格范围内，防止索引越界。

测试样例说明 #

以第一个样例输入为例：

• 起点S到M的最短路径耗时6秒，小于给定的9秒，所以输出成功；
  第二个样例中，要么找不到M的路径，要么最短时间大于等于5秒，所以输出失败。

内容的提问来源于stack exchange，提问作者BananaHacker