题目链接
分析： 把十把钥匙的状态进行二进制压缩，然后就是bfs了。 坑点就是两个点之间可能有很多门，一个地方可能有多把钥匙。之前一直WA，我看了题解才做对＝ ＝
代码：
#include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <stack> #include <queue> using namespace std; int N, M, P; const int dx[] = {0, 1, 0, -1}; const int dy[] = {1, 0, -1, 0}; const int INF = 0x3f3f3f3f; int g[55][55][55][55]; int mp[55][55]; bool vis[55][55][1 << 11]; struct Node { int x, y, t, d; }; bool valid(int x, int y) { return (x >= 1 && x <= N && y >= 1 && y <= M); } int bfs() { memset(vis, false, sizeof(vis)); queue<Node> q; q.push((Node){1, 1, mp[1][1], 0}); vis[1][1][mp[1][1]] = true; while (!q.empty()) { Node x = q.front(); q.pop(); // cout<<x.x<<" "<<x.y<<" "<<x.t<<endl; if (x.x == N && x.y == M) return x.d; for (int k = 0; k < 4; k ++) { int tmpx = x.x + dx[k]; int tmpy = x.y + dy[k]; if (!valid(tmpx, tmpy)) continue; int key = g[x.x][x.y][tmpx][tmpy]; if (key == INF) continue; if ((key & x.t) != key) continue; int tmpt = x.t | mp[tmpx][tmpy]; if (vis[tmpx][tmpy][tmpt]) continue; vis[tmpx][tmpy][tmpt] = true; q.push((Node){tmpx, tmpy, tmpt, x.d + 1}); } } return -1; } int main(int argc, char const *argv[]) { while(~scanf("%d%d%d", &N, &M, &P)) { memset(g, 0, sizeof(g)); memset(mp, 0, sizeof(mp)); int k; scanf("%d", &k); for (int i = 0; i < k; i ++) { int a, b, c, d, e; scanf("%d%d%d%d%d", &a, &b, &c, &d, &e); g[a][b][c][d] |= 1 << e; g[c][d][a][b] |= 1 << e; if (!e) g[a][b][c][d] = g[c][d][a][b] = INF; } scanf("%d", &k); for (int i = 0; i < k; i ++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); mp[a][b] |= 1 << c; } cout<<bfs()<<endl; } return 0; }