孤岛营救问题
https://www.luogu.org/problemnew/show/P4011
用状压DP标记拿到钥匙的数量
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #include<vector> 8 #include<cstdio> 9 using namespace std; 10 11 int n,m,p; 12 int dir[4][2]={1,0,0,1,-1,0,0,-1}; 13 int door[15][15][15][15]; 14 int map[15][15]; 15 int book[15][15][1<<12]; 16 struct sair{ 17 int x,y,step,key; 18 }; 19 20 void bfs(){ 21 sair s,e; 22 s.x=1,s.y=1,s.key=map[1][1],s.step=0; 23 queue<sair>Q; 24 book[1][1][0]=1; 25 Q.push(s); 26 while(!Q.empty()){ 27 s=Q.front(); 28 Q.pop(); 29 for(int i=0;i<4;i++){ 30 e.x=s.x+dir[i][0]; 31 e.y=s.y+dir[i][1]; 32 if(e.x>=1&&e.x<=n&&e.y>=1&&e.y<=m&&(door[s.x][s.y][e.x][e.y]!=0)){ 33 if(e.x==n&&e.y==m){ 34 cout<<s.step+1<<endl; 35 return; 36 } 37 if((door[s.x][s.y][e.x][e.y]>0)&&((s.key&door[s.x][s.y][e.x][e.y])>0)){ 38 int tmp=s.key; 39 if(!book[e.x][e.y][tmp]){ 40 book[e.x][e.y][tmp]=1; 41 e.step=s.step+1; 42 e.key=s.key; 43 if(map[e.x][e.y]){ 44 e.key|=map[e.x][e.y]; 45 } 46 Q.push(e); 47 } 48 } 49 else if(door[s.x][s.y][e.x][e.y]==-1){ 50 int tmp=s.key; 51 if(!book[e.x][e.y][tmp]){ 52 book[e.x][e.y][tmp]=1; 53 e.step=s.step+1; 54 e.key=s.key; 55 if(map[e.x][e.y]){ 56 e.key|=map[e.x][e.y]; 57 } 58 Q.push(e); 59 } 60 } 61 } 62 } 63 } 64 cout<<-1<<endl; 65 return; 66 } 67 68 int main(){ 69 cin>>n>>m>>p; 70 int k; 71 cin>>k; 72 int x1,x2,y1,y2,G; 73 memset(door,-1,sizeof(door)); 74 for(int i=1;i<=k;i++){ 75 cin>>x1>>y1>>x2>>y2>>G; 76 if(!G){ 77 door[x1][y1][x2][y2]=0; 78 door[x2][y2][x1][y1]=0; 79 } 80 else{ 81 door[x1][y1][x2][y2]=(1<<G); 82 door[x2][y2][x1][y1]=(1<<G); 83 } 84 } 85 cin>>k; 86 for(int i=1;i<=k;i++){ 87 cin>>x1>>y1>>G; 88 map[x1][y1]|=(1<<G); 89 } 90 bfs(); 91 }