鏈接：https://ac.nowcoder.com/acm/problem/22344
來源：牛客網(wǎng)

精通程序設(shè)計(jì)的 Applese 雙寫了一個(gè)游戲。

在這個(gè)游戲中，它被困在了一個(gè) n×m 的迷宮中，它想要逃出這個(gè)迷宮。

在迷宮中，有一些方格是水池，只有當(dāng) Applese 處于水屬性的時(shí)候才可以通過；有一些方格是巖漿，只有當(dāng) Applese 是火屬性的時(shí)候可以通過；有一些方格是墻壁，無論如何都無法通過；另一些格子是空地（包括起點(diǎn)和終點(diǎn)），可以自由通過。

在一些空地上有神秘道具可以讓 Applese 轉(zhuǎn)換自己的屬性（從水屬性變?yōu)榛饘傩曰驈幕饘傩宰優(yōu)樗畬傩?#xff0c;需要一個(gè)單位的時(shí)間）。

已知 Applese 在一個(gè)單位的時(shí)間內(nèi)可以朝四個(gè)方向行走一格，且開始處于水屬性，位于空地的道具拾取后只能在該處立即使用（或者不使用），且可以多次使用。求它走出迷宮需要的最少時(shí)間。
輸入描述:
第一行兩個(gè)正整數(shù) n, m 表示迷宮的大小。
接下來 n 行，每行長度為 m 的字符串。描述地圖。
其中 ‘S’ 表示起點(diǎn)，‘T’ 表示終點(diǎn)，’.’ 表示空地，‘w’表示巖漿，’~‘表示水池，’@’ 表示道具，’#'表示障礙。
保證地圖中的起點(diǎn)和終點(diǎn)只有一個(gè)，道具都位于空地。

5 5 .w@.. .S#.. ~w#.. .w..~ @w.~T

輸出：

18

備注:
1≤n,m≤100
Ac_code:

#include <stdio.h> #include <queue> const int maxn = 105; using namespace std; int n,m,sx,sy,ex,ey; struct point {int x,y;int now, step;bool operator <(const point &p)const{return step > p.step;} }; char mp[maxn][maxn]; bool vis[maxn][maxn][2]; int dx[]= {-1,1,0,0},dy[]= {0,0,-1,1}; int bfs() {point s;s.x = sx,s.y = sy;s.now = 0,s.step = 0;vis[s.x][s.y][s.now] = true;priority_queue<point>q;q.push(s);while(!q.empty()){point k = q.top();q.pop();if(k.x==ex&&k.y==ey){return k.step;}point t;for(int i = 0; i < 4; i++){t.x = k.x + dx[i];t.y = k.y + dy[i];t.now = k.now;t.step = k.step + 1;if(t.x<0||t.x>=n||t.y<0||t.y>=m)continue;if(mp[t.x][t.y]=='#')continue;if(!vis[t.x][t.y][t.now]){if(mp[t.x][t.y]=='.'||mp[t.x][t.y]=='S'||mp[t.x][t.y]=='T'||mp[t.x][t.y]=='@'){vis[t.x][t.y][t.now] = true;q.push(t);}else if((mp[t.x][t.y]=='~'&&k.now==0)||(mp[t.x][t.y]=='w'&&k.now==1)){vis[t.x][t.y][t.now] = true;q.push(t);}}if(mp[k.x][k.y]=='@'){t.now = !k.now;if(vis[t.x][t.y][t.now])continue;if((mp[t.x][t.y]=='~'&&t.now==1)||(mp[t.x][t.y]=='w'&&t.now==0))//這里要注意continue;t.step = k.step+2;vis[t.x][t.y][t.now] = true;q.push(t);}}}return -1; } int main() {scanf("%d%d",&n,&m);for(int i = 0; i < n; i++){scanf("%s",mp[i]);for(int j = 0; j < m; j++){if(mp[i][j]=='S'){sx = i;sy = j;}else if(mp[i][j]=='T'){ex = i;ey = j;}}}printf("%d\n",bfs());return 0; }

總結(jié)

以上是生活随笔為你收集整理的Applese 走迷宫（优先队列+bfs）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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