Python解决算法题【魔塔游戏】

昨天同事发来一道C++算法题，说是他5年级儿子的作业不会做，让我帮忙看一下。啥？5年级跟C++这两个词现在已经联系到一起了嘛，再看题目，顿时有点恍惚，一种梦回大学ACM的感觉：

问题描述

在魔塔游戏中，一位魔王抓走了公主，并把她关在魔王设计的地牢里面。一位勇士找到了公主，要在被魔王发现之前，带公主离开地牢。地牢是由n x m的格子构成，并在地平的某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始勇士带子公主在(sx,sy)的位置，离开地车的门在(ex,ey)的位置，由于带着公主，勇士每秒钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t秒钟回地牢视察一次，若发现个公主不在原位置便把会发现。经过勇士的探察，已知道整个地牢的地图。现在请你帮他计算能否成功带着公主逃离。只要在魔王下次视察之前走到出口就算离开地牢，如果魔王回来的时候刚好走到出口或还未到出口部算逃亡失败。

输入

输入第一行有三个整数n,m,t(2<n,m<=20,t>0)，接下来的n行m列为地牢的地图，其中包括：
. 代表路
# 代表墙
@ 代表公主(勇士)的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j 
a-j 代表钥匙,对应的门分别为A-J

输出

在单独的一行中输出一个整数。
如果可以成功逃亡，请输出需要多少秒钟才能离开，如果不能则输出-1

输入样例

4 5 17 
@A.B.
a#.#.
#..#^
c..b#

输出样例

16

好吧，先不说小学5年级为什么会有这样子的作业，C++也已经忘的差不多了。不过题目还是蛮有意思的，今天闲来无事，试着用熟悉的Python来解一下。

先说下解题思路，题目描述的花里胡哨，其实就是一个求最短路径的问题，众所周知，无权图求最短路径，首先考虑广度优先搜索算法（BFS），即从起点开始，上下左右各走一步，然后判断是否可以通行，是的话，以新的位置为起点，继续上下左右各走一步，依此递推，直到触发结束条件（到达出口或者时间到）。还是众所周知，BFS算法配合队列结构实现比手搓递推函数要方便的多，由于Python已经内置了队列的数据结构（deque），到这里其实已经成功了一小半了。当然这道题里多了一个逻辑判断，就是钥匙的持有状态决定了门是否可以通行，因此在搜索过程中，对于遍历的每一节点进行访问状态判断时，需要加上一个钥匙状态，即有钥匙状态下跟无钥匙状态下处于同一位置时属于两个不同的状态，以确保取完钥匙后可以原路返回去开门。讲起来有点绕，还是老规矩，321上代码~

本程序不需要用到任何第三方库，引用内置的collections包中的deque类就行：

from collections import deque

首先定义一个方法start_game(n, m, t, map)，算法逻辑都在这个方法中实现，输入参数即题目要求的n，m，t和地图，地图用一个n行m列的二元数组表示。首先定义两个变量，然后遍历地图，记录起点和出口，用二元组坐标表示：

def start_game(n, m, t, map):

    start = end = ()
    for i in range(n):
        for j in range(m):
            if map[i][j] == '@':
                start = (i, j)
            if map[i][j] == '^':
                end = (i, j)

然后定义一个队列（成员类型为[x, y, keys, steps]，其中x和y表示当前位置坐标，keys是一个钥匙列表，steps用于记录到达当前坐标所用的步数），和一个记录访问状态的列表（成员类型为[x, y, keys]，含义同上），并赋初始值，即起点坐标及空钥匙状态。

    queue = deque()
    queue.append([start[0], start[1], [], 0])
    visited = []
    visited.append([start[0], start[1], []])

然后就是依次出队开始遍历，将队列成员中的x,y,keys,steps赋与对应变量。设定游戏结束条件，当步数大于t时，表示这条路已经无法在规定时间内走出，跳过当前节点，继续下个节点的遍历；当坐标等于出口坐标时，表示顺利走出，直接返回steps即可；当队列为空时结束循环，表示所有的都不通，在循环外return -1即可：

    while queue:
        x, y, keys, steps = queue.popleft()

        if steps >= t:
            continue

        if (x, y) == end:
            return steps

        #后续代码见下文

    return -1

当遍历继续时，则向上下左右四个方向各走一步，我在这里直接定义了一个向量数组，然后再做一次循环，使坐标能够朝上下左右四个方向各移动一次：

        moving = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        for move_x, move_y in moving:
            new_x, new_y = x + move_x, y + move_y

然后根据地图数据的类型进行判断，决定下一步是否能够通行。首先确保新坐标在地图范围内，超出地图范围则直接跳过；当遇到#符号时，表示遇到墙，不可通行，跳过循环，当遇到A-J时，表示遇到门，此时需要判断是否持有相应的钥匙，即a-j，当keys列表中不含门对应的小写字母的钥匙，则无法通行，跳过循环；当遇到a-j时，表示拿到钥匙，此时需要copy一份keys列表到new_keys列表，然后添加钥匙。需要注意的是，keys由于在其他循环中会用到，不能直接用等号复制，因为列表变量是指针类型，必须使用copy()方法生成一个新列表，不然会引起错乱：

            if 0 <= new_x < n and 0 <= new_y < m:
                position = map[new_x][new_y]

                if position == '#':
                    continue

                if 'A' <= position <= 'J' and position.lower() not in keys:
                    continue

                new_keys = keys.copy()
                if 'a' <= position <= 'j' and position not in keys:
                    new_keys.append(position)

当路径可通行时且当前状态未访问过时，将新节点加入队列，并对steps+1，以保证在下次队列循环时再继续遍历，同时将访问状态加入访问状态记录列表：

                if [new_x, new_y, new_keys] not in visited:
                    visited.append([new_x, new_y, new_keys])
                    queue.append([new_x, new_y, new_keys, steps + 1])

如此，只需静待所有循环结束，即可完成遍历，输出结果。我们写个main函数来测试一下：

if __name__ == '__main__':
    n, m, t = 4, 5, 17
    map = [
        '@A.B.',
        'a#.#.',
        '#..#^',
        'c..b#'
    ]

    print(start_game(n, m, t, map))

运行成功，得到结果：

E:\PycharmProjects\算法题\.venv\Scripts\python.exe E:\PycharmProjects\算法题\魔塔游戏.py 
16

进程已结束，退出代码为 0

作者：小娇GPT