记录一个进阶版迷宫题

题目概述

给一个 n * m 的迷宫, 其中有 q 对传送阵, 没传送一次需要耗时 3 个单位 , 求起点到终点对最短路径.

思路

这道题和普通的迷宫题有些许不同之处, 主要在于存在传送阵. 传送阵可能会导致存在一些点 可能多次遍历到 并且可能 下次遍历时路径更短 所以使用一个 mark 数组记录路径长度(从起点到当前点的路径长度) 然后在遍历过程中维护这个数组. 具体维护思路如下:

• mark 数组默认全为 无穷大 float('inf')
• 找到起始点后将起始点的 mark 值标为 0
• 每当遍历到一个点后, 判断当前路径长度是否大于 mark 数组中的值
  • 如果大于, 则遍历当前点能够到达的点
  • 如果小于, 则仅仅将当前点踢出队列

需要注意的是, 由于不能保证终点在第一次遍历到时路径最小, 所以需要等到队列为空时才可以结束循环.

代码

from collections import deque

n, m, q = [int(item) for item in input().split(' ')]
graph = []
for _ in range(n):
    graph.append(list(input()))

# 标记数组默认值为无穷大，使得所有第一次到达的点都可以刷新标记数组
mark = [[float('inf') for _ in range(m)] for _ in range(n)]


def check(a: int, b: int) -> bool:
    if 0 <= a < n and 0 <= b < m and graph[a][b] != '#':
        return True
    return False


# 使用字典(入口 -> 出口列表) 记录传送门
te = {}
for _ in range(q):
    x1, y1, x2, y2 = [int(item) for item in input().split(' ')]
    if (x1, y1) not in te:
        te[(x1, y1)] = []
    if (x2, y2) not in te:
        te[(x2, y2)] = []
    te[(x1, y1)].append((x2, y2))
    te[(x2, y2)].append((x1, y1))

# 使用队列记录bfs搜索的状态
de = deque()
path = [[1, 0], [-1, 0], [0, 1], [0, -1]]

endX, endY = 0, 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'S':
            de.appendleft([i, j, 0])
        if graph[i][j] == 'T':
            endX, endY = i, j

while len(de) != 0:
    # 取出队列最后的数据
    x, y, index = de[-1]

    # 判断是否走过，若走过，则判断当前路径是否更短，更短则搜索当前点
    if index < mark[x][y]:
        mark[x][y] = index

        # 再判断是否可以传送
        if (x, y) in te:
            for nextX, nextY in te[(x, y)]:
                if check(nextX, nextY):
                    de.appendleft([nextX, nextY, index + 3])

        # 再将周围可以进入的点加入队列中
        for nextX, nextY in [[x + pathX, y + pathY] for pathX, pathY in path]:
            if check(nextX, nextY):
                de.appendleft([nextX, nextY, index + 1])

    # 最后删除队列中的元素
    de.pop()

if mark[endX][endY] != float('inf'):
    print(mark[endX][endY])
else:
    print(-1)

总结

在写这种需要考虑的事情比较多的题目时, 可以尝试先编写注释, 然后再编写代码. 这样能够有效防止遗漏情况,也便于出现 debug.