勝利大逃亡(續)

Time Limit: 4000/2000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10137????Accepted Submission(s): 3664


Problem Description Ignatius再次被魔王抓走了(搞不懂他咋這么討魔王喜歡)……

這次魔王汲取了上次的教訓，把Ignatius關在一個n*m的地牢里，并在地牢的某些地方安裝了帶鎖的門，鑰匙藏在地牢另外的某些地方。剛開始Ignatius被關在(sx,sy)的位置，離開地牢的門在(ex,ey)的位置。Ignatius每分鐘只能從一個坐標走到相鄰四個坐標中的其中一個。魔王每t分鐘回地牢視察一次，若發現Ignatius不在原位置便把他拎回去。經過若干次的嘗試，Ignatius已畫出整個地牢的地圖。現在請你幫他計算能否再次成功逃亡。只要在魔王下次視察之前走到出口就算離開地牢，如果魔王回來的時候剛好走到出口或還未到出口都算逃亡失敗。

Input 每組測試數據的第一行有三個整數n,m,t(2<=n,m<=20,t>0)。接下來的n行m列為地牢的地圖，其中包括:

. 代表路
* 代表墻
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表帶鎖的門,對應的鑰匙分別為a-j
a-j 代表鑰匙，對應的門分別為A-J

每組測試數據之間有一個空行。

Output 針對每組測試數據，如果可以成功逃亡，請輸出需要多少分鐘才能離開，如果不能則輸出-1。

Sample Input 4 5 17 @A.B. a*.*. *..*^ c..b* 4 5 16 @A.B. a*.*. *..*^ c..b*
Sample Output 16 -1
Author LL
Source ACM暑期集訓隊練習賽（三）
Recommend linle

思路：

1.因為有10種不同的鑰匙，每種都有兩種狀態，結合二進制的特點，
剛好把這10把鑰匙當成每一個位，要 1<<10 個位保存所有的狀態


2.模擬撿起鑰匙，撿起鑰匙就是說明這個位上的數字變成1狀態
所以想到位運算 |，改變這個點的狀態


3.模擬碰到門的情況，就和這個位置上的位&一次，

結果是1代表有鑰匙，可以開門?

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int maxn=20+10; char map[maxn][maxn]; int n,m,t; bool vis[maxn][maxn][(1<<10)+10]; //狀態壓縮，最多有10種鑰匙 int dx[]={-1,1,0,0}; int dy[]={0,0,-1,1}; struct Point {int x,y,step;int key; }; queue<Point>Q; Point st; bool check(int x,int y) {if(x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]!='*')return true;return false; } int bfs() {while(!Q.empty()) Q.pop();memset(vis,false,sizeof(vis));vis[st.x][st.y][st.key]=true;st.key=st.step=0;Q.push(st);Point cur,nex;while(!Q.empty()){cur=Q.front();Q.pop();if(map[cur.x][cur.y]=='^')return cur.step;for(int i=0;i<4;i++){nex.x=cur.x+dx[i];nex.y=cur.y+dy[i];nex.key=cur.key;if(check(nex.x,nex.y)){nex.step=cur.step+1;if(nex.step>=t)continue;else if(map[nex.x][nex.y]>='A'&&map[nex.x][nex.y]<='Z'){int temp=map[nex.x][nex.y]-'A';//int nk=cur.key&(1<<temp);int nk=cur.key&1<<temp;//先左移，后與運算 if(nk&&!vis[nex.x][nex.y][nex.key]){vis[nex.x][nex.y][nex.key]=true;Q.push(nex);}}else if(map[nex.x][nex.y]>='a'&&map[nex.x][nex.y]<='z'){int temp=map[nex.x][nex.y]-'a';//nex.key=cur.key|(1<<temp);nex.key=cur.key|1<<temp;//先左移，后或運算 if(!vis[nex.x][nex.y][nex.key]){vis[nex.x][nex.y][nex.key]=true;Q.push(nex);}}else{if(!vis[nex.x][nex.y][nex.key]){vis[nex.x][nex.y][nex.key]=true;Q.push(nex);}}//else}//if}//for}return -1; } inline void read_graph() {char str[maxn];for(int i=1;i<=n;i++){scanf("%s",str+1);for(int j=1;j<=m;j++){if(str[j]=='@'){st.x=i;st.y=j;map[i][j]=str[j];}else map[i][j]=str[j];} } } int main() {while(~scanf("%d%d%d",&n,&m,&t)){read_graph();int ans=bfs();printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 1429 胜利大逃亡(续) bfs+状态压缩的全部內容，希望文章能夠幫你解決所遇到的問題。

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