題干：

小z身處在一個(gè)迷宮中，小z每分鐘可以走到上下左右四個(gè)方向的相鄰格之一。迷宮中有一些墻和障礙物。
同時(shí)迷宮中也有一些傳送門，當(dāng)小z走到任意一個(gè)傳送門時(shí)，可以選擇傳送到其他任意的傳送門(傳送是不花費(fèi)時(shí)間的)，
當(dāng)然也可以停留在原地。現(xiàn)在小z想知道走出迷宮需要花費(fèi)的最少時(shí)間。

Input

輸入第一行為組數(shù)T(t<=10)。
對(duì)于每組數(shù)據(jù)第一行為兩個(gè)整數(shù)R和C(1<=R,C<=100)。以下R行每行有C個(gè)字符，即迷宮地圖。
其中"#"代表墻和障礙物，"."表示空地，"P"表示傳送門，"Z"表示小z的起始位置，"W"表示迷宮出口。
對(duì)于每組數(shù)據(jù)保證起始位置和迷宮出口唯一。

Output

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

Sample Input

2
3 4
.Z..
.P#.
##PW
4 4
Z..P
....
##..
W#.P

Sample Output

2
IMPOSSIBLE

解題報(bào)告：

? ? 裸。bfs復(fù)習(xí)。

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 using namespace std; const int MAX = 2e3 + 5; struct N {int x,y;N(){}N(int x,int y):x(x),y(y){} } p[MAX]; struct Node {int x,y;int t;Node(){}Node(int x,int y,int t):x(x),y(y),t(t){} }; bool vis[505][505]; int tot,r,c; char maze[505][505]; int nx[4] = {0,1,0,-1}; int ny[4] = {1,0,-1,0}; int bfs(N st,N ed) {queue<Node> q;q.push(Node(st.x,st.y,0));while(q.size()) {Node cur = q.front();q.pop();if(cur.x == ed.x && cur.y == ed.y) return cur.t;if(vis[cur.x][cur.y]) continue;vis[cur.x][cur.y] = 1;for(int k = 0; k<4; k++) {int tx = cur.x + nx[k];int ty = cur.y + ny[k];if(tx < 1 || tx > r || ty < 1 || ty > c) continue;if(maze[tx][ty] == '#') continue;q.push(Node(tx,ty,cur.t+1));}if(maze[cur.x][cur.y] == 'P') {for(int l = 1; l<=tot; l++) {if(p[l].x == cur.x && p[l].y == cur.y) continue;q.push(Node(p[l].x,p[l].y,cur.t));}}}return -1; } int main() {int t;cin>>t;while(t--) {tot=0;memset(vis,0,sizeof vis);scanf("%d%d",&r,&c);for(int i = 1; i<=r; i++) {scanf("%s",maze[i] + 1);}int stx,sty,edx,edy;for(int i = 1; i<=r; i++) {for(int j = 1; j<=c; j++) {if(maze[i][j] == 'Z') stx = i,sty = j;if(maze[i][j] == 'W') edx = i,edy = j;if(maze[i][j] == 'P') p[++tot] = N(i,j);}}int ans = bfs(N(stx,sty),N(edx,edy));if(ans == -1) printf("IMPOSSIBLE\n");else printf("%d\n",ans);} return 0 ; } /* 14:46 - 14:57 */

?

總結(jié)

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

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