思路与算法

用状态(格子,钥匙集合)做BFS。每格可能有多把钥匙，用位或汇总，进入格子时立即免费取得全部钥匙。相邻格之间缺省互通；标记0的边为墙，正数为对应门，只有钥匙集合包含该位才可走。每次移动耗时1，首次到达右下角就输出距离；穷尽状态仍未到达输出-1。

正确性说明

钥匙没有丢弃代价或负作用，拿取耗时0，所以一到格子就拿全不会使任何后续路径变差。给定格子与钥匙集合，未来允许的移动完全确定，状态充分。每条允许边都对应一次真实移动；所有真实行走也可按自动取钥匙规范化成状态路径。BFS在单位边图中按距离递增发现状态，首次终点距离就是最短营救时间。

复杂度

格子V=nm≤100，钥匙状态2^p≤1024。距离初始化O(V2^p)，最多每状态枚举4个方向，时间O(V2^p+k+s)，另有V²门表初始化。空间O(V*2^p+V²)，包含BFS队列；p≤10。输入钥匙条目数s虽未单列上界，但逐条位或处理O(s)、不保存原列表。

易错点

没有记录的相邻边是通路，不能全部默认墙。墙与无门通路必须区分；同一格可以有多把钥匙，也可以在起点直接拿钥匙。无解必须输出-1。门是双向的，钥匙不会在开门后消耗。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, p, k;
    cin >> n >> m >> p >> k;
    int cells = n * m, states = 1 << p;
    vector<vector<int>> door(cells, vector<int>(cells, -1));
    for (int i = 0; i < k; ++i) {
        int a, b, c, d, g;
        cin >> a >> b >> c >> d >> g;
        int u = (a - 1) * m + b - 1, v = (c - 1) * m + d - 1;
        door[u][v] = door[v][u] = g;
    }
    vector<int> key(cells);
    int s;
    cin >> s;
    while (s--) {
        int x, y, q;
        cin >> x >> y >> q;
        key[(x - 1) * m + y - 1] |= 1 << (q - 1);
    }
    vector<int> dist(cells * states, -1);
    queue<pair<int, int>> q;
    dist[key[0]] = 0;
    q.push({0, key[0]});
    int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        int u = cur.first, mask = cur.second, d = dist[u * states + mask];
        if (u == cells - 1) {
            cout << d << '\n';
            return 0;
        }
        for (int z = 0; z < 4; ++z) {
            int x = u / m + dx[z], y = u % m + dy[z];
            if (x < 0 || x >= n || y < 0 || y >= m)
                continue;
            int v = x * m + y, g = door[u][v];
            if (g == 0 || (g > 0 && !(mask & (1 << (g - 1)))))
                continue;
            int next = mask | key[v];
            if (dist[v * states + next] < 0) {
                dist[v * states + next] = d + 1;
                q.push({v, next});
            }
        }
    }
    cout << -1 << '\n';
}