孤岛营救问题
https://www.luogu.org/problemnew/show/P4011
用状压DP标记拿到钥匙的数量
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
using namespace std; int n,m,p;
int dir[][]={,,,,-,,,-};
int door[][][][];
int map[][];
int book[][][<<];
struct sair{
int x,y,step,key;
}; void bfs(){
sair s,e;
s.x=,s.y=,s.key=map[][],s.step=;
queue<sair>Q;
book[][][]=;
Q.push(s);
while(!Q.empty()){
s=Q.front();
Q.pop();
for(int i=;i<;i++){
e.x=s.x+dir[i][];
e.y=s.y+dir[i][];
if(e.x>=&&e.x<=n&&e.y>=&&e.y<=m&&(door[s.x][s.y][e.x][e.y]!=)){
if(e.x==n&&e.y==m){
cout<<s.step+<<endl;
return;
}
if((door[s.x][s.y][e.x][e.y]>)&&((s.key&door[s.x][s.y][e.x][e.y])>)){
int tmp=s.key;
if(!book[e.x][e.y][tmp]){
book[e.x][e.y][tmp]=;
e.step=s.step+;
e.key=s.key;
if(map[e.x][e.y]){
e.key|=map[e.x][e.y];
}
Q.push(e);
}
}
else if(door[s.x][s.y][e.x][e.y]==-){
int tmp=s.key;
if(!book[e.x][e.y][tmp]){
book[e.x][e.y][tmp]=;
e.step=s.step+;
e.key=s.key;
if(map[e.x][e.y]){
e.key|=map[e.x][e.y];
}
Q.push(e);
}
}
}
}
}
cout<<-<<endl;
return;
} int main(){
cin>>n>>m>>p;
int k;
cin>>k;
int x1,x2,y1,y2,G;
memset(door,-,sizeof(door));
for(int i=;i<=k;i++){
cin>>x1>>y1>>x2>>y2>>G;
if(!G){
door[x1][y1][x2][y2]=;
door[x2][y2][x1][y1]=;
}
else{
door[x1][y1][x2][y2]=(<<G);
door[x2][y2][x1][y1]=(<<G);
}
}
cin>>k;
for(int i=;i<=k;i++){
cin>>x1>>y1>>G;
map[x1][y1]|=(<<G);
}
bfs();
}