解释都存在代码中了

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <deque>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

//E 竖n(n - 1) * 2(横着) * 2 (两边通过) = 360, E开400
const int N = 11, M = N * N, E = 400, P = 1 << 10;

int n, m, p, k;
int h[M], e[E], w[E], ne[E], idx;//邻接表
int g[N][N], key[M];//g[][]二维坐标变成一维，key[]表示这有哪些钥匙
int dist[M][P];//[]到每个点,[]每种状态  的距离
bool st[M][P];//判重

set<PII> edges;//存一下当前将哪些边加上了

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void build()
{
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            for (int u = 0; u < 4; u ++ )
            {
                int x = i + dx[u], y = j + dy[u];
                if (!x || x > n || !y || y > m) continue;
                int a = g[i][j], b = g[x][y];//拿出对应编号
                if (edges.count({a, b}) == 0)//没有出现过的话
                    add(a, b, 0);//可通过
            }
}

int bfs()
{
    memset(dist, 0x3f, sizeof dist);//初始距离
    dist[1][0] = 0;//起点为0

    deque<PII> q;//建立双端队列
    q.push_back({1, 0});//编号1的点加进去且没有钥匙

    while (q.size())
    {
        PII t = q.front();//取出队头
        q.pop_front();

        if (st[t.x][t.y]) continue;//出来过的话，continue
        st[t.x][t.y] = true;

        if (t.x == n * m) return dist[t.x][t.y];
        //已经找到最短路径了
        //第一次找到，一定是最小值

        if (key[t.x])//如果有钥匙
        {
            int state = t.y | key[t.x];//加入钥匙
            //看是否可以少点距离，从而替换
            if (dist[t.x][state] > dist[t.x][t.y])
            {
                dist[t.x][state] = dist[t.x][t.y];
                q.push_front({t.x, state});//加入队头
            }
        }

        //这里有墙的边不会枚举到，因为没加进去
        for (int i = h[t.x]; i != -1; i = ne[i])
        {
            int j = e[i];//j存一下这个邻边编号是多少

            //移位一个缩小空间
            //w[i] 不为零的话，表示有门，
            //!(t.y >> w[i] - 1 & 1) 表示没有钥匙
            if (w[i] && !(t.y >> w[i] - 1 & 1)) continue;

            //更新下一个点（节点编号为j的点）
            if (dist[j][t.y] > dist[t.x][t.y] + 1)
            {
                dist[j][t.y] = dist[t.x][t.y] + 1;
                q.push_back({j, t.y});
            }
        }
    }

    return -1;//没找到，返回-1
}

int main()
{
    cin >> n >> m >> p >> k;

    //坐标x,y变成一个数了
    for (int i = 1, t = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            g[i][j] = t ++ ;

    memset(h, -1, sizeof h);//清空表头
    while (k -- )//读入k条边
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        int a = g[x1][y1], b = g[x2][y2];//找到编号
        edges.insert({a, b}), edges.insert({b, a});//表示用过了
        if (c) add(a, b, c), add(b, a, c);//是门，建一个类型
        //是墙的话不用管它
    }

    build();//将没有出现的边建立上

    int s;
    cin >> s;
    while (s -- )
    {
        int x, y, id;
        cin >> x >> y >> id;
        //并，或起来，有1出1，多加进去，偏移量从0开始，节省空间
        key[g[x][y]] |= 1 << id - 1;
    }

    cout << bfs() << endl;//遍历

    return 0;
}