題目鏈接：點擊查看

題目大意：給出一個n*m的迷宮，其中有一些邊為不可逾越的墻，有一些邊為不同型號的門，而鑰匙會分布在迷宮的不同位置，求從點(1,1)到點(n,m)的最短時間

題目分析：出現在網絡流里的一道題目。。但是一道很裸的bfs+狀壓，因為不同門的類型給的特別少，只有10種，如果bfs的話時間復雜度也才n*m*2^10，直接搜索就好了

注意一下幾個坑點：

鑰匙是永久性的而不是一次性的

一個點可以有多把鑰匙

起點也可以有鑰匙

然后就是簡單的bfs了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=15;const int b[4][2]={0,1,0,-1,1,0,-1,0};int n,m;int maze[N][N][N][N];//maze[x1][y1][x2][y2]之間是否有墻/門int key[N][N];//key[x][y]有哪些鑰匙 bool vis[N][N][(1<<N)];//標記狀態struct Node {int x,y,step,state;Node(int X,int Y,int STEP,int STATE){x=X;y=Y;step=STEP;state=STATE;} };int bfs() {memset(vis,false,sizeof(vis));queue<Node>q;q.push(Node(1,1,0,key[1][1]));vis[1][1][key[1][1]]=true;while(q.size()){Node cur=q.front();q.pop();if(cur.x==n&&cur.y==m)return cur.step;for(int i=0;i<4;i++){int xx=cur.x+b[i][0];int yy=cur.y+b[i][1];if(xx<=0||yy<=0||xx>n||yy>m)continue;int door=maze[cur.x][cur.y][xx][yy];if(door==-1)//墻 continue;if(door&&!(cur.state&(1<<door)))//沒鑰匙 continue;if(vis[xx][yy][cur.state|key[xx][yy]])continue;vis[xx][yy][cur.state|key[xx][yy]]=true;q.push(Node(xx,yy,cur.step+1,cur.state|key[xx][yy]));}}return -1; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int p;scanf("%d%d%d",&n,&m,&p);int k;scanf("%d",&k);while(k--){int x1,x2,y1,y2,g;scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);if(g)//門 maze[x1][y1][x2][y2]=maze[x2][y2][x1][y1]=g;else//墻 maze[x1][y1][x2][y2]=maze[x2][y2][x1][y1]=-1;}scanf("%d",&k);while(k--){int x,y,g;scanf("%d%d%d",&x,&y,&g);key[x][y]|=(1<<g);}printf("%d\n",bfs());return 0; }

?

總結

以上是生活随笔為你收集整理的洛谷 - P4011 孤岛营救问题(bfs+状态压缩)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。