題干：

小z身處在一個迷宮中，小z每分鐘可以走到上下左右四個方向的相鄰格之一。迷宮中有一些墻和障礙物。
同時迷宮中也有一些怪獸，當小z碰到任意一個怪獸時，小z需要將怪獸消滅掉才可以離開此方格。但消滅
怪獸會花費一定的時間。現在小z想知道走出迷宮需要花費的最少時間。

Input

輸入第一行為組數T(T<=10)。

對于每組數據第一行為兩個整數R和C(1<=R,C<=200)。以下R行每行有C個字符，即迷宮地圖。

其中"#"代表墻和障礙物，"."表示空地，[1~9]的數字代表此處有怪獸以及消滅此處的怪獸需要的時間.

"Z"表示小z的起始位置，"W"表示迷宮出口。

對于每組數據保證起始位置和迷宮出口唯一。

Output

對于每組數據，輸出走出迷宮的最短時間(單位:分鐘)。如果無法走出迷宮則輸出"IMPOSSIBLE"。

Sample Input

2
3 4
.Z..
.234
#.W.
4 4
Z.1.
.32.
##4.
W#..

Sample Output

5
IMPOSSIBLE

Hint

解題報告：

? ? ?優先隊列搞一波pq，如果是普通的bfs，那么隊列即可，因為隊列就能保證取出來的Node結構體的t是最小值，但是這題不一樣，所以需要pq。剛開始寫的時候wa了好幾發最后發現是main函數中那個雙層循環的內層循環寫成了for(int j=i; j<=m; j++)、、、我也是醉了好像不止第一次錯在這里了、、、

AC代碼：

#include<cstdio> #include<queue> #include<cstring> #include<cmath> #include<map> #include<iostream> #include<algorithm> #define ll long long using namespace std; struct Node {int x,y;int t;Node(){}Node(int x,int y,int t):x(x),y(y),t(t){} bool operator<(const Node b) const{return t > b.t;} }; int n,m; int nx[4]={0,1,0,-1}; int ny[4]={1,0,-1,0}; bool vis[205][205]; char maze[205][205]; int bfs(int sx,int sy) {priority_queue<Node> pq;pq.push(Node(sx,sy,0));Node cur;int tx,ty;while(pq.size()) {cur=pq.top();pq.pop(); for(int k = 0; k<4; k++) {tx = cur.x + nx[k];ty = cur.y + ny[k];if(maze[tx][ty] == '#' || vis[tx][ty] || tx < 1 || tx > n || ty < 1 || ty > m) continue;vis[tx][ty]=1;if(maze[tx][ty] == 'W') return cur.t + 1;else if(maze[tx][ty] == '.') pq.push(Node(tx,ty,cur.t+1));else pq.push(Node(tx,ty,cur.t + 1 + maze[tx][ty] - '0'));}}return -1;} int main() {int t,sx,sy;cin>>t;while(t--) {scanf("%d%d",&n,&m);memset(vis,0,sizeof vis);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] == 'Z') {sx=i,sy=j;break;}}}int ans = bfs(sx,sy);if(ans == -1) puts("IMPOSSIBLE");else printf("%d\n",ans);}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【HRBUST - 1621】迷宫问题II （bfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

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