题目描述：
这是一个 n 行 m 列的迷宫，某些格子有若干枚钥匙。相邻格子之间有一扇门，门上有若干把锁，所有的锁都打开才能够通行，若没有锁则直接通行。对应的钥匙可以打开对应的锁，钥匙和锁的类型范围由数字 0 到 p 表示。每一步可以走到周围四连通的格子之一，门可以从两个方向打开，捡钥匙和开锁不消耗时间。问从 (1, 1) 到 (n, m) 最少需要走多少步。
输入格式：
第一行三个整数 n，m，p 。
第二行一个整数 K ，
接下来 K 行每行 5 个整数 x1, y1, x2, y2, t ，表示 (x1, y1) 与 (x2, y2) 之间的门上有一把 t 类型的锁。
保证 (x1, y1) 与 (x2, y2) 相邻。
下一行一个整数 S ，表示钥匙的个数。
接下来 S 行每行三个整数 x, y, t ，表示 x,y 处有一枚 t 类型的钥匙。
输出格式：
输出一行表示答案。
样例输入：
4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2
4 2 1
样例输出：
14
数据规模：
N,M,P≤10,K<150,S≤150
思路
状态压缩：将钥匙的拥有情况表示为二进制下第 k 位的 0 或 1 。有就是1，无就是0
例如有0，2，3钥匙，则二进制表示为 1101 。
然后就是bfs了。以下是几个位运算的小技巧
- s & 1 << k > 0 ：二进制下第 k 位是不是1。
- s | = 1 << k ：二进制下将第 k 位变为1。
- (s&t)==t ：检查二进制下 s 中是否包含 t 。
位运算YYDS！以上操作均可以在十进制下进行。
状态设计： dis[x][y][k] 表示在拥有k表示的钥匙的情况下到x,y的最短距离。 vis[x][y][k] 表示是否在拥有k表示的钥匙串的情况下经过 (x,y) 。最后如何求出最小的距离呢？只需要遍历 k （从 0 到 2^{11} ）然后找最小的 dis[n][m][k] 。发现答案还是初始值说明无法到达呗，输出 -1 。
AC Code
#include <bits/stdc++.h>
using namespace std;
struct node{
int x,y,k;
};
queue<node> q;
int n,m,p,k,s,x,y;
bool vis[15][15][2050];
int door[15][15][15][15],key[15][15],dis[15][15][2050];
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int main(){
scanf("%d%d%d",&n,&m,&p);
scanf("%d",&k);
for(int i=1;i<=k;i++){
int x1,x2,y1,y2,t;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &t);
door[x1][y1][x2][y2] |= (1 << t);
door[x2][y2][x1][y1] |= (1 << t);
}
scanf("%d",&s);
for(int i=1;i<=s;i++){
int x,y,t;
scanf("%d%d%d",&x,&y,&t);
key[x][y] |= (1 << t);
}
memset(dis,0x3f,sizeof(dis));
dis[1][1][key[1][1]]=0;
vis[1][1][key[1][1]]=true;
q.push((node){1,1,key[1][1]});
while(!q.empty()){
node now=q.front();
q.pop();
int x=now.x,y=now.y,k=now.k;
for(int i=0;i<4;i++){
int nx=x+d[i][0],ny=y+d[i][1];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && (k&door[x][y][nx][ny])==door[x][y][nx][ny]) {
int nk=k|key[nx][ny];
if(!vis[nx][ny][nk]){
vis[nx][ny][nk]=true;
dis[nx][ny][nk]=dis[x][y][k]+1;
q.push((node){nx,ny,nk});
}
}
}
}
int ans=dis[0][0][0];
for(int i=0;i<2048;i++){
ans=min(ans,dis[n][m][i]);
}
if(ans==dis[0][0][0]) cout<<"-1"<<endl;
else cout<<ans<<endl;
return 0;
}