1689: 營(yíng)救小明
時(shí)間限制: 1 Sec 內(nèi)存限制: 32 MB
[提交][狀態(tài)][討論版]
題目描述
一天，小明夢(mèng)見自己被外星人抓走了，他被關(guān)在了一座監(jiān)獄里，這座監(jiān)獄形如N*M（N,M<=200）的矩陣，監(jiān)獄里有墻、道路和守衛(wèi)。
小明的小伙伴們得知他被外星人抓走后想要把他救出來，他們要試圖接近關(guān)押小明的那間房間。當(dāng)他們經(jīng)過有守衛(wèi)的房間時(shí)他們必須干掉守衛(wèi)后繼續(xù)前進(jìn)，而當(dāng)遇到墻的時(shí)候則只能繞道。他們只能向上下左右四個(gè)方向移動(dòng)，每移動(dòng)一次耗時(shí)1分鐘，干掉一個(gè)守衛(wèi)也耗時(shí)1分鐘。不必?fù)?dān)心，他們足夠強(qiáng)壯，可以干掉任何一個(gè)守衛(wèi)。
現(xiàn)在請(qǐng)你計(jì)算出他們當(dāng)中最快到達(dá)小明所在房間的那個(gè)人最短需要花費(fèi)多長(zhǎng)時(shí)間。
輸入
輸入包含多組測(cè)試數(shù)據(jù)。
每組輸入的第一行是兩個(gè)整數(shù)N和M（N,M<=200）。
接下來N行，每行輸入M個(gè)字符。“.”代表道路，可以通行。“#”代表墻。“g”代表守衛(wèi)。“m”代表小明所在的房間。“f”代表每一個(gè)小明的小伙伴，可能有多個(gè)小伙伴一起來救他。
輸出
對(duì)于每組輸入，輸出小伙伴當(dāng)中最快到達(dá)小明所在房間的那個(gè)人最短需要花費(fèi)多長(zhǎng)時(shí)間。如果所有小伙伴都無法到達(dá)小明所在的房間的話，請(qǐng)輸出“Poor Xiaoming”（引號(hào)不輸出）。
樣例輸入

7 8 #.#####. #.m#..f. #..#g... ..#..#.# #...##.. .#...... ........

樣例輸出

13

提示
來源
/*
逆向思維。
讓小明去找朋友，最先找的朋友所用的時(shí)間到就是ans
同時(shí)需要用優(yōu)先隊(duì)列，時(shí)間少的優(yōu)先
*/

#include <bits/stdc++.h>using namespace std; typedef long long LL; const LL INF = 0x3f3f3f3f; char mp[205][205]; struct Map {int x,y;LL step;bool operator<(const Map a)const{return step>a.step;} } s; int n,m; LL ans; bool vis[205][205]; int step_x[]={-1,1,0,0},step_y[]={0,0,-1,1}; LL bfs(Map s) {priority_queue<Map>q;vis[s.x][s.y] = true;q.push(s);while(!q.empty()){Map t = q.top();q.pop();if(mp[t.x][t.y]=='f'){return t.step;}Map tt;for(int i = 0; i < 4; i++){tt.x = t.x + step_x[i];tt.y = t.y + step_y[i];if(tt.x<0||tt.x>=n||tt.y<0||tt.y>=m) continue;if(mp[tt.x][tt.y]!='#'&&!vis[tt.x][tt.y]){if(mp[tt.x][tt.y]=='g'){tt.step = t.step + 2;}else{tt.step = t.step + 1;}vis[tt.x][tt.y] = true;q.push(tt);}}}return INF; } int main() {while(~scanf("%d%d",&n,&m)){for(int i = 0; i < n; i++){scanf("%s",mp[i]);for(int j = 0; j < m; j++){vis[i][j] = false;if(mp[i][j]=='m'){s.x = i;s.y = j;s.step = 0;}}}ans = bfs(s);if(ans == INF){printf("Poor Xiaoming\n");}else{printf("%lld\n",ans);}}return 0; } 與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的1689: 营救小明（bfs+priority_queue逆向思维）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。