首先关于分层图思想详见2004的这个论文
https://wenku.baidu.com/view/dc57f205cc175527072208ad.html
这道题可以用状态压缩，我们对于每一把钥匙的状态只有两种，获得了或者没有获得，然后就可以用二进制方法表示，例如一共有5把钥匙，我们如果用二进制数01001表示当前状态，就意味着我们已经拥有了第一类钥匙，第四类钥匙（从右往左看），然后我们就可以把此时的状态压缩为一个int了，节省了很多的空间，具体的操作就用位运算实现。
然后就是简单粗暴的dfs过程。
不过有几个点需要注意
① 要加反边。
② 一个位置可能有多个钥匙，注意要用位与运算。
下面给出代码。
1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 using namespace std; 5 const int N = 20; 6 7 struct Node{ 8 int x, y, step, state; 9 }; 10 int n, m, p, t, tt, map[N][N][N][N], key[N][N], vis[N][N][1 << 11]; 11 int py[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; 12 13 inline int bfs(){ 14 queue < Node > q; 15 q.push((Node){1, 1, 0, key[1][1]}); 16 while(!q.empty()){ 17 Node u = q.front(); q.pop(); 18 if (u.x == n && u.y == m) return u.step; 19 for (int i = 0; i < 4; i++){ 20 int x = u.x + py[i][0]; 21 int y = u.y + py[i][1]; 22 if (x > 0 && x <= n && y > 0 && y <= m) 23 if (map[u.x][u.y][x][y] == -1) continue; 24 else if((map[u.x][u.y][x][y] == 0) || (1 << (map[u.x][u.y][x][y] - 1)) & u.state){ 25 int states = u.state | key[x][y]; 26 if (!vis[x][y][states]){ 27 q.push((Node){x, y, u.step + 1, states}); 28 vis[x][y][states] = 1; 29 } 30 } 31 } 32 } 33 return -1; 34 } 35 36 37 38 int main(){ 39 while(~scanf("%d %d %d",&n, &m, &p)){ 40 scanf("%d", &t); 41 memset(map, 0, sizeof(map)); 42 memset(key, 0, sizeof(key)); 43 memset(vis, 0, sizeof(vis)); 44 for (int i = 0; i < t; i++){ 45 int a, b, c, d, e; 46 scanf("%d %d %d %d %d", &a, &b, &c, &d, &e); 47 map[a][b][c][d] = map[c][d][a][b] = (e == 0)?-1:e; 48 } 49 scanf("%d", &tt); 50 for (int i = 0; i < tt; i++){ 51 int a, b, c; 52 scanf("%d %d %d", &a, &b, &c); 53 key[a][b] |= (1 << (c - 1)); 54 } 55 printf("%d ", bfs()); 56 } 57 return 0; 58 }