/******************以下思路来自百度菜鸟的程序人生*********************/
bfs即可，可能有多个’r’，而’a’只有一个，从’a’开始搜，找到的第一个’r’即为所求
需要注意的是这题宽搜时存在障碍物，遇到’x’点是，时间+2，如果用普通的队列就
并不能保证每次出队的是时间最小的元素，所以要用优先队列，第一次用优先队列，还不熟练哇
优先队列(priority_queue)的基本操作：
empty(); 队列为空返回1
pop(); 出队
push(); 入队
top(); 返回队列中优先级最高的元素
size(); 返回队列中元素的个数
/**************************************************************/
修改了学妹的代码，增加了优先队列，成功AC~
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> using namespace std; char map[205][205]; bool visit[205][205]; int xx[5]={1,-1,0,0}; int yy[5]={0,0,1,-1}; int n,m,x,y; struct node { int x,y; int time; friend bool operator < (const node &a,const node &b) { return a.time>b.time; } }; void bfs(int &min) { priority_queue<node>q; int i; node step,temp; step.x=x; step.y=y; step.time=0; visit[x][y]=true; q.push(step); while(!q.empty()) { step=q.top(); q.pop(); if(map[step.x][step.y]=='r') { min=step.time; return ; } else if(map[step.x][step.y]!='r') { for(i=0;i<4;i++) { if(map[step.x+xx[i]][step.y+yy[i]]!='#' && !visit[step.x+xx[i]][step.y+yy[i]]) { if(map[step.x+xx[i]][step.y+yy[i]]=='x') { temp.x=step.x+xx[i]; temp.y=step.y+yy[i]; temp.time=step.time+2; } else { temp.x=step.x+xx[i]; temp.y=step.y+yy[i]; temp.time=step.time+1; } visit[temp.x][temp.y]=true; q.push(temp); } } } } } int main() { while(~scanf("%d %d",&n,&m)) { int i,j; int min=50000; memset(visit,false,sizeof(visit)); for(i=0;i<=n+1;++i) map[i][0]=map[i][m+1]='#'; for(i=0;i<=m+1;++i) map[0][i]=map[n+1][i]='#'; for(i=1;i<=n;++i) { for(j=1;j<=m;j++) { cin>>map[i][j]; if(map[i][j]=='a') { x=i; y=j; } } } bfs(min); if(min<50000) printf("%d ",min); else printf("Poor ANGEL has to stay in the prison all his life. "); } return 0; }