題干：

?

精通程序設計的 Applese 雙寫了一個游戲。

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

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

在一些空地上有神秘道具可以讓 Applese 轉換自己的屬性（從水屬性變為火屬性或從火屬性變為水屬性，需要一個單位的時間）。

?

已知 Applese 在一個單位的時間內可以朝四個方向行走一格，且開始處于水屬性，位于空地的道具拾取后只能在該處立即使用（或者不使用），且可以多次使用。求它走出迷宮需要的最少時間。

輸入描述:

第一行兩個正整數 n, m 表示迷宮的大小。 接下來 n 行，每行長度為 m 的字符串。描述地圖。 其中 'S' 表示起點，'T' 表示終點，'.' 表示空地，'w'表示巖漿，'~'表示水池，'@' 表示道具，'#'表示障礙。 保證地圖中的起點和終點只有一個，道具都位于空地。

輸出描述:

輸出一個整數，表示 Applese 走出迷宮的最短時間。特別地，如果 Applese 走不出迷宮，輸出 "-1"。

示例1

輸入

復制

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

輸出

復制

18

備注:

1≤n,m≤100

?

解題報告：

? ?直接bfs就行了，，注意要用pq，，不能直接用隊列、、之前在這里就栽過坑。。。還有啊，，根據樣例，起點是可以重復走的、、（代碼雖然挺好看但是還是比較冗長的、、）

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; char maze[505][505]; bool vis[505][505][2];//0:水 1：火 int nx[4] = {0,1,0,-1}; int ny[4] = {1,0,-1,0}; struct Node {int x,y;int t;bool q;Node(){}Node(int x,int y,int t,bool q):x(x),y(y),t(t),q(q){}bool operator<(const Node b) const{return t > b.t;} }; int n,m; int edx,edy,stx,sty; bool ok(int x,int y) {if(x >=1 && x <= n && y >= 1 && y <= m) return 1;else return 0 ; } int bfs(int stx,int sty) {priority_queue<Node> q;q.push(Node(stx,sty,0,0));vis[stx][sty][0] = 1;while(q.size()) {Node cur = q.top();q.pop();if(cur.x == edx && cur.y == edy) return cur.t;for(int k = 0; k<4; k++) {int tx = cur.x + nx[k];int ty = cur.y + ny[k];if(!ok(tx,ty)) continue;if(maze[tx][ty] == 'T') return cur.t+1;if(maze[tx][ty] == '.') {if(vis[tx][ty][cur.q] == 0) vis[tx][ty][cur.q] = 1, q.push(Node(tx,ty,cur.t+1,cur.q));}if(maze[tx][ty] == 'w') {if(vis[tx][ty][cur.q] == 0 && cur.q == 1) vis[tx][ty][cur.q] = 1, q.push(Node(tx,ty,cur.t+1,cur.q));}if(maze[tx][ty] == '~') {if(vis[tx][ty][cur.q] == 0 && cur.q == 0) vis[tx][ty][cur.q] = 1, q.push(Node(tx,ty,cur.t+1,cur.q));}if(maze[tx][ty] == '#') continue;if(maze[tx][ty] == '@') {if(vis[tx][ty][cur.q] == 0) vis[tx][ty][cur.q] = 1, q.push(Node(tx,ty,cur.t+1,cur.q));if(vis[tx][ty][!cur.q] == 0) vis[tx][ty][!cur.q] = 1, q.push(Node(tx,ty,cur.t+2,!cur.q));}}}return -1; } int main() {cin>>n>>m;for(int i = 1; i<=n; i++) {scanf("%s",maze[i]+1);}for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {if(maze[i][j] == 'S') stx = i, sty = j,maze[i][j] = '.';if(maze[i][j] == 'T') edx = i, edy = j;}}int ans = bfs(stx,sty);printf("%d\n",ans);return 0 ;}

?

總結

以上是生活随笔為你收集整理的【牛客 - 330C】Applese 走迷宫（bfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

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