題目描述

機場是一個很肥的地方，所以想跳一波機場，看看到底有多肥。不過機場雖然肥，但是跳的人也多。小明第一次跳機場，剛跳下來就到處都是槍聲，小明嚇得快要哭出來了，想逃離機場，emmm，還是打野比較適合他。
現在把機場看作一個二維平面，’.‘代表可以走的空地，’@'代表小明當前的位置，'x’代表這里是個障礙物，'o’代表這里有個敵人，并且手里有槍，敵人可以攻擊上下左右四個方向，小明只要走到或者一開始就在敵人可以攻擊的位置，就會死亡(機場個個都是98K爆頭dalao)，子彈不會穿過障礙物，敵人不會移動。小明只能往上下左右走，每走一步需要1秒，只要小明移動到機場的邊緣再走一步就算逃離了機場，現在小明請你幫他找一條最快逃離機場的線路，輸出這個時間，如果怎么都逃不出去，輸出"no zuo no die!"(不含引號)。

輸入格式

多組測試數據，首先第一行一個整數T，代表測試數據組數。1≤T≤100。
每組測試數據有n,m(1≤n,m≤200)，代表機場是一個n×m的方陣,接下來是一個由’.’,’@’,‘x’,‘o’構成的n×m的方陣，’@'只有一個。

輸出格式

對于每組數據輸出一個數代表最快需要多少時間逃出機場，或者"no zuo no die!"

輸入樣例

3
5 5
.x.x.
.x.x.
…
…@…
.o.o.
3 3
@…
xxx
o.x
3 3
o.o
.@.
.x.

輸出樣例

4
1
no zuo no die!

解題思路

200*200的數據量優先考慮廣搜，注意初始化敵人攻擊路徑標記為無后序性，注意多組輸入

AC代碼

萌新記錄成長，大佬勿噴 #include <bits/stdc++.h> using namespace std; const int maxn=205; char mp[maxn][maxn]; bool book[maxn][maxn]; int n,m; int dir[4][2]={1,0,-1,0,0,1,0,-1}; struct cp{int x,y;}emp[maxn*maxn];//敵人數組 struct stu{int x,y,t;stu(int xx,int yy,int tt):x(xx),y(yy),t(tt){}};//廣搜隊列 int bfs(int si,int sj) {queue <stu> myq;book[si][sj]=1;myq.push(stu(si,sj,0));while(!myq.empty()){stu temp=myq.front();for(int i=0;i<4;i++){int tx=temp.x+dir[i][0];int ty=temp.y+dir[i][1];if(tx<0||tx>=n||ty<0||ty>=m){return temp.t;}if(mp[tx][ty]=='x'||book[tx][ty]==1){continue;}book[tx][ty]=1;myq.push(stu(tx,ty,temp.t+1));}myq.pop();}return -1; } bool start_die(int x,int y)//判斷是否落地成盒 {for(int i=x+1;i<n;i++)if(mp[i][y]=='o')return true;else if(mp[i][y]=='x')break;for(int i=x-1;i>=0;i--)if(mp[i][y]=='o')return true;else if(mp[i][y]=='x')break;for(int i=y+1;i<m;i++)if(mp[x][i]=='o')return true;else if(mp[x][i]=='x')break;for(int i=y-1;i>=0;i--)if(mp[x][i]=='o')return true;else if(mp[x][i]=='x')break;return false; } void init(int x,int y)//將敵人射程都變成走過的路 {book[x][y]=1;for(int i=x+1;i<n;i++)if(mp[i][y]=='x')break;else book[i][y]=1;for(int i=x-1;i>=0;i--)if(mp[i][y]=='x')break;else book[i][y]=1;for(int i=y+1;i<m;i++)if(mp[x][i]=='x')break;else book[x][i]=1;for(int i=y-1;i>=0;i--)if(mp[x][i]=='x')break;else book[x][i]=1; } int main() {int T;while(cin>>T){while(T--){cin>>n>>m;int si,sj;int k=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++){cin>>mp[i][j];if(mp[i][j]=='@')//取出生地為si,sj{si=i;sj=j;}if(mp[i][j]=='o'){emp[k].x=i;emp[k].y=j;k++;}}if(start_die(si,sj))//判斷是否落地成盒{cout<<"no zuo no die!"<<endl;}else{memset(book,0,sizeof(book));for(int i=0;i<k;i++)//將敵人的攻擊范圍設置為走過的路{init(emp[i].x,emp[i].y);}int ans=bfs(si,sj);//廣搜if(ans==-1){cout<<"no zuo no die!"<<endl;}elsecout<<ans+1<<endl;}}}return 0; }

總結

以上是生活随笔為你收集整理的BTTCOJ 问题 C: 逃离机场 广度优先搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

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