因为要求的是最少的时间，很明显的是一个利用优先队列的bfs的题目，题目很一般。
#include"iostream"
#include"algorithm"
#include"stdio.h"
#include"string.h"
#include"cmath"
#include"queue"
#define mx 205
using namespace std;
int n,m,sx,sy,ex,ey;
int dir[][]={{,},{,-},{-,},{,}};
char map1[mx][mx];
struct node
{
int x,y,steps;
friend bool operator<(node a,node b)
{
return b.steps<a.steps;
}
};
bool judge(int x,int y)
{
if(x>=&&x<n&&y>=&&y<m&&map1[x][y]!='#') return true;
return false;
}
void bfs()
{
node cur,next;
cur.x=sx;cur.y=sy;cur.steps=;
int i;
priority_queue<node>q;
q.push(cur);
while(!q.empty())
{
cur=q.top();
q.pop();
if(cur.x==ex&&cur.y==ey){cout<<cur.steps<<endl;return;}
for(i=;i<;i++)
{
next.x=cur.x+dir[i][];
next.y=cur.y+dir[i][];
if(judge(next.x,next.y))
{
if(map1[next.x][next.y]=='x')
{
next.steps=cur.steps+;
}
else next.steps=cur.steps+;
map1[next.x][next.y]='#';
q.push(next);
}
}
}
cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
}
int main()
{
while(scanf("%d%d",&n,&m)==)
{
int i,j;
for(i=;i<n;i++)
for(j=;j<m;j++)
{
cin>>map1[i][j];
if(map1[i][j]=='r') {sx=i;sy=j;map1[i][j]='#';}
else if(map1[i][j]=='a') {ex=i;ey=j;map1[i][j]='.';}
}
bfs();
}
return ;
}