Saving Tang Monk

题面

有宽度不超过 100 的正方形迷宫如下所示,“K”代表开始孙悟空所处的位置，T代表唐僧所处的位置， .代表空地 #代表墙 S代表此处有一条蛇，数字 n 代表此处有钥匙且要是的种类编号是 1-9。孙悟空要去救唐僧，他只能朝上、下、左、由四个方向走，走到相邻的格子需要花1。#处不能走。走到S处则需要停留 1。走到放钥匙处，如果钥匙的种类编号为n，且孙悟空已经得到了编号为 1, 2, …, n-1 的钥匙，则它可以取走该钥匙，否则就只能过而不取。一共有 m 种钥匙 1-9，孙悟空走到唐僧处时，必须集齐 m 种钥匙才能救唐僧，否则只能过而不救。问孙悟空要救唐僧，最少要花多长时间。

样例输入

3 1
K . S
# # 1
1 # T
3 1
K # T
. S #
1 # .
3 2
K # T
. S .
2 1 .
0 0

样例输出

5
impossible
8

AC代码和思路

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <queue>

using namespace std;

const int N = 110;

struct node {
    int x, y, k, d;  // 节点的位置坐标、已收集的钥匙数量、到达当前位置的步数
    node(int xx, int yy, int kk, int dd) { x = xx; y = yy; k = kk; d = dd; }  // 构造函数用于初始化节点
    friend bool operator<(node a, node b) {
        return a.d > b.d;  // 重载<运算符，用于优先队列的排序，根据步数从小到大排序
    }
};

int n, m, ans;  // 迷宫的大小、钥匙的数量、最短路径的长度
int kx, ky, tx, ty;  // 起始点和目标点的坐标
char s[N][N];  // 存储迷宫的地图
bool st[N][N][15];  // 记录已访问的状态，第三维表示已收集的钥匙数量
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};  // 上下左右四个方向的偏移量
priority_queue<node> q;  // 优先队列，用于广度优先搜索

int bfs() {
    node start(kx, ky, 0, 0);  // 起始节点

    st[kx][ky][0] = true;  // 标记起始节点已访问

    q.push(start);  // 将起始节点加入队列

    while (!q.empty()) {
        node t = q.top(); q.pop();  // 取出队首节点
        int x = t.x, y = t.y, key = t.k, d = t.d;  // 获取节点的信息

        if (x == tx && y == ty && key == m)  // 如果当前节点是目标节点，并且已经收集了所有的钥匙
            ans = min(ans, d);  // 更新最短路径的长度

        for (int j = 0; j < 4; j++) {  // 遍历四个方向
            int xx = x + dx[j], yy = y + dy[j];  // 计算下一个节点的坐标

            // 判断下一个节点是否合法，即在迷宫范围内，不是墙壁且没有访问过
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && s[xx][yy] != '#' && !st[xx][yy][key]) {
                char c = s[xx][yy];
                int kk = 0, ss = 1;
                if (c == 'S') ss++;
                if (c - '0' - key == 1) kk++;

                // 将下一个节点加入队列，更新已收集的钥匙数量和步数，并标记已访问
                q.push(node(xx, yy, key + kk, d + ss));
                st[xx][yy][key] = true;
            }
        }
    }
    return 0;
}

int main() {
    while (cin >> n >> m && n && m) {
        ans = 0x3f3f3f3f;  // 初始化最短路径长度为一个很大的值

        memset(st, 0, sizeof st);  // 清空已访问的状态数组

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                cin >> s[i][j];  // 读取迷宫的地图

                // 记录起始点和目标点的坐标
                if (s[i][j] == 'K') kx = i, ky = j;
                if (s[i][j] == 'T') tx = i, ty = j;
            }

        bfs();  // 进行广度优先搜索

        if (ans == 0x3f3f3f3f)
            cout << "impossible" << "\n";  // 无法到达目标点
        else
            cout << ans << "\n";  // 输出最短路径的长度

        while (!q.empty())
            q.pop();  // 清空队列
    }
    return 0;
}