链接：?m=ProblemSet&a=showProblem&problem_id=1613
Description ：小z身处在一个迷宫中，小z每分钟可以走到上下左右四个方向的相邻格之一。迷宫中有一些墙和障碍物。同时迷宫中也有一些传送门，当小z走到任意一个传送门时，可以选择传送到其他任意的传送门(传送是不花费时间的)，当然也可以停留在原地。现在小z想知道走出迷宫需要花费的最少时间。Input ：输入第一行为组数T(t<=10)。对于每组数据第一行为两个整数R和C(1<=R,C<=100)。以下R行每行有C个字符，即迷宫地图。其中"#"代表墙和障碍物，"."表示空地，，"P"表示传送门，"Z"表示小z的起始位置，"W"表示迷宫出口。对于每组数据保证起始位置和迷宫出口唯一。Output ：对于每组数据，输出走出迷宫的最短时间(单位:分钟)。如果无法走出迷宫则输出"IMPOSSIBLE"。
Sample Input ：23 4.Z…P#.##PW4 4Z..P….##..W#.PSample Output ：2IMPOSSIBLE解析：
BFS + priority_queue
代码解析如下：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <set>#include <queue>#include <algorithm>#define MAXN 205#define RST(N)memset(N, 0, sizeof(N))using namespace std;typedef struct _Node{int x, y;int step;}Node;Node p[MAXN], start;char Map[MAXN][MAXN];int v[MAXN][MAXN];int n, m, res, cas;int Sx, Sy, Ex, Ey, k;const int dx[] = {-1, 0, 1, 0};const int dy[] = {0, 1, 0, -1};priority_queue <Node> pq;bool operator < (Node a, Node b){return a.step > b.step;}bool check(int x, int y){return x>=0 && y>=0 && x<n && y<m && Map[x][y]!='#' && !v[x][y];}int BFS(){Node cur;int px, py, xx, yy, cstep;while(!pq.empty()) {cur = pq.top(), pq.pop();px = cur.x, py = cur.y, cstep = cur.step;for(int i=0; i<4; i++) {xx = px + dx[i], yy = py + dy[i];if(check(xx, yy)) {if(xx == Ex && yy == Ey) return cstep+1;if(Map[xx][yy] == 'P') {for(int j=0; j<k; j++) { //飞到另外没有访问过的传送门所在的位置；int fx = p[j].x, fy = p[j].y;if(!v[fx][fy]) {cur.x = fx, cur.y = fy;cur.step = cstep + 1;pq.push(cur);}}}else if(Map[xx][yy] == '.') {cur.x = xx, cur.y = yy;cur.step = cstep + 1;pq.push(cur);}v[xx][yy] = 1;}}}return -1;}int main(){scanf("%d", &cas);while(cas–) {scanf("%d %d", &n, &m);k = 0;for(int i=0; i<n; i++) {scanf("%s", Map[i]);for(int j=0; j<m; j++) {if(Map[i][j] == 'Z') { Sx=i, Sy=j; }else if(Map[i][j] == 'W') { Ex=i, Ey=j; }else if(Map[i][j] == 'P') { //记录传送门的位置p[k].x = i, p[k].y = j;p[k++].step = 0;}}}RST(v);v[Sx][Sy] = 1;while(!pq.empty()) pq.pop();start.x = Sx, start.y = Sy, start.step = 0;pq.push(start);res = BFS();if(res != -1) printf("%d\n", res);else printf("IMPOSSIBLE\n");}return 0;}
当你感到悲哀痛苦时，最好是去学些什么东西。
