题目地址：?pid=1242
这道题目我是用BFS+优先队列做的。听说只用bfs会超时。
因为这道题有多个营救者，所以我们从被营救者开始bfs，找到最近的营救者就是最短时间。
先定义一个结构体，存放坐标x和y，还有到达当前点（x,y）消耗的时间。
struct node {int x,y;int time;friend bool operator < (const node &a,const node &b){//时间少的放在队列前面return a.time>b.time;}};
注意时间少的先出列。
重点讲一下bfs的过程，当前格子命名为now，走过的下一个格子命名为next，先将起点赋值给now然后入队。
now.x=x;now.y=y;now.time=0;//源点走到源点时间初始为0vis[now.x][now.y]=1;que.push(now);//源点入队
之后只要队列不为空，就取出队列的头节点，判断是否为终点也就是任意一个r，如果是r，则返回到达当前节点所需时间即:now.time；若不是r，那接下来把now的四个方向全部遍历一百，如果不是墙就将其加入队列，，并且把当前time更新：next.time=now.time+delta。delta的值遇到x就是2，否则是1。一直循环直到que.top出来的坐标代表的是r。
若队列为空即找完了全图都没找到r，那就返回-1，代表无法解救。
好了贴个代码：
#include <iostream>#include <cstdio>#include <cstring>#include <queue>using namespace std;int n,m;int vis[202][202];char map[202][202];int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};struct node {int x,y;int time;friend bool operator < (const node &a,const node &b){//时间少的放在队列前面return a.time>b.time;}};int can_go(int x,int y){if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]!='#'){return 1;}else return 0;}int bfs(int x,int y){int i;node now,next;priority_queue<node>que;memset(vis,0,sizeof(vis));now.x=x;now.y=y;now.time=0;//源点走到源点时间初始为0vis[now.x][now.y]=1;que.push(now);//源点入队while(!que.empty()){now=que.top();que.pop();if(map[now.x][now.y]=='r'){return now.time;}for(i=0;i<4;i++){next.x=now.x+dir[i][0];next.y=now.y+dir[i][1];if(can_go(next.x,next.y)&&!vis[next.x][next.y]){vis[next.x][next.y]=1;if(map[next.x][next.y]=='x'){next.time=now.time+2;}else {next.time=now.time+1;}que.push(next);}}}return -1;}int main(){int ans;int i,j;int x,y;while(scanf("%d%d",&n,&m)!=EOF){for(i=0;i<n;i++){scanf("%s",map[i]);}for(i=0;i<n;i++)for(j=0;j<m;j++)if(map[i][j]=='a'){x=i;y=j;break;}ans=bfs(x,y);if(ans==-1){printf("Poor ANGEL has to stay in the prison all his life.\n");}else {printf("%d\n",ans);}}return 0;}
版权声明：欢迎转载，转载时请在文章开头注明出处
像一颗深绿色的宝石镶嵌在云南大地上，
