普通队列每一次出队列的元素只是步数上最优，但不一定是时间上最优的，这时即使我们把整个迷宫搜完以最小值作为最优依然不行，因为每一步处理完成都会把该状态标记为已处理vis[i][j]=1，因此，只要有一步不是最优，就会影响后面的结果。这题的正确做法是优先队列，每一次出队都是出时间最少的，这样可以保证每一步最优，并且一旦搜到目标即可立刻结束。
3 3
#a.
.x.
.r#
比如这个图，node(int x,int y,int time) 第一次入队:node(0,1,0), 第二次node(0,2,1),node(1,1,2) 出队选择时间最少的 node(0,2,1) 第三次入队 node(1,2,2) 出队:node(1,2,2) node(0,2,1) ，这样时间最少的始终最先出，理解了优先队列出队顺序后面就简单啦~
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
/*
3 3
#a.
.x.
.r#
*/
using namespace std;
char map[205][205];
int vis[205][205];
int m,n;
int d[4][2]= {0,-1,0,1,-1,0,1,0};
struct node
{
int x,y;
int time;
friend bool operator<(const node &a,const node &b)//运算符重载对优先队列里的小于号进行的重载
{
return a.time>b.time;//时间小的先出队
}
};
int bfs(int x,int y)
{
node st,nt;
priority_queue<node> q;
st.x=x;
st.y=y;
st.time=-1;
q.push(st);
vis[st.x][st.y]=1;
while(!q.empty())
{
st=q.top();
q.pop();
if(map[st.x][st.y]=='r')
return st.time;
for(int i=0; i<4; i++)
{
nt.x=st.x+d[i][0];
nt.y=st.y+d[i][1];
if(!vis[nt.x][nt.y] && nt.x>=0 && nt.x<m && nt.y>=0 && nt.y<n && map[nt.x][nt.y]!='#')
{
vis[nt.x][nt.y]=1;
if(map[nt.x][nt.y]=='.')
nt.time=st.time+1;
else
nt.time=st.time+2;
q.push(nt);
}
}
}
return -1;
}
int main()
{
int x,y,count;
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(vis,0,sizeof(vis));
count=-1;
for(int i=0; i<m; i++)
scanf("%s",map[i]);
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
if(map[i][j]=='a')
{
x=i;
y=j;
break;
}
count=bfs(x,y);
if(count==-1)
printf("Poor ANGEL has to stay in the prison all his life.\n");
else
printf("%d\n",count);
}
return 0;
}
