逃離機場

題目描述
小明聽說機場是一個很肥的地方，所以想跳一波機場，看看到底有多肥。不過機場雖然肥，但是跳的 人也多。小明第一次跳機場，剛跳下來就到處都是槍聲，小明嚇得快要哭出來了，想逃離機場，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!

首先分析題目，很明顯是一道搜索題目，并且是一道不確定出口的搜索題目，當小明只要走出迷宮就可以，就是說只要搜索到可以走出地圖就可以，因為找的是最短路徑，所以使用BFS廣度搜索尋找最短路徑，DFS找出口的話不一定是最短。
題目有坑不好好理解題意的話是肯定有數據是不過不去的。狙擊手會四個方向開槍，意思是狙擊手所在位置的四個方向直到障礙物都是不可以走的，或者說，給你的地圖就是人已經在狙擊手的搶線上了，就是說人上來就已經被打死了，一步都走不了。這就是最坑的地方，所以在輸入數據之后就要預處理一下，然后在進行BFS搜索。把狙擊手的四個槍線初始化，如果遇到障礙物子彈無法穿過，狙擊手到障礙物之間的路徑是不可以走的。預處理之后找到人并且人還是活著的，然后BFS找最短的出口，活著并且逃出去才可以，人死了或找不到出口都是不可以的，只能輸出no zuo no die!

#include<iostream> #include<queue> #include<cstring> using namespace std; int t,sx,sy,n,m,alive,out; char mat[205][205]; int book[205][205]; int dir[][2] = {-1,0,0,1,1,0,0,-1}; struct node{int x,y,s; }; void mark(int x,int y){book[x][y] = 1;for(int i=0;i<4;i++){int tx = x;int ty = y;while(1){tx = tx + dir[i][0];ty = ty + dir[i][1];if(tx < 0 || tx >= n || ty < 0 || ty >= m || mat[tx][ty] == 'x')break;if(mat[tx][ty] == '.' || mat[tx][ty] == '@')book[tx][ty] = 3;}} } int bfs(int x,int y){node front,tail;queue<node> q;front.x = x;front.y = y;front.s = 0;q.push(front);while(!q.empty()){front = q.front();q.pop();for(int i=0;i<4;i++){int tx = front.x + dir[i][0];int ty = front.y + dir[i][1];if(tx < 0 || tx >=n || ty < 0 || ty >= m){out = 1;return front.s+1;}if(mat[tx][ty] == '.' && book[tx][ty] == 0){tail.x = tx;tail.y = ty;tail.s = front.s+1;book[tx][ty] = 1;q.push(tail);}}}return 0; } int main(){cin>>t;while(t--){alive = out = 0;cin>>n>>m;memset(book,0,sizeof book);for(int i=0;i<n;i++){cin>>mat[i];}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(mat[i][j] == 'x')book[i][j] = 2;if(mat[i][j] == 'o')mark(i,j);}}for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(mat[i][j] == '@' && book[i][j] == 0){sx = i;sy = j;book[i][j] = 1;alive = 1;} // for(int i=0;i<n;i++){ // for(int j=0;j<m;j++) // cout<<book[i][j]; // cout<<endl; // }int step = bfs(sx,sy);if(alive && out)cout<<step<<endl;if(!alive || !out)cout<<"no zuo no die!"<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的ACM算法-逃离机场的全部內容，希望文章能夠幫你解決所遇到的問題。

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