直接把Angle的位置作为起点，广度优先搜索即可，这题不是步数最少，而是time最少，就把以time作为衡量标准，加入优先队列，队首就是当前time最少的。遇到Angle的朋友就退出。只需15ms
AC代码：
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=202;
int d[maxn][maxn];
int n,m;
char G[maxn][maxn];
struct node{
int x,y;
node(){
}
node(int x,int y):x(x),y(y){
}
bool operator <(const node &p)const{
return d[x][y]>d[p.x][p.y];
}
}s;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int bfs(){
memset(d,-1,sizeof(d));
priority_queue<node>q;
d[s.x][s.y]=0;
q.push(s);
while(!q.empty()){
node p=q.top();
q.pop();
int x=p.x,y=p.y;
if(G[x][y]=='r') return d[x][y];
for(int i=0;i<4;++i){
int px=x+dx[i],py=y+dy[i];
if(px<0||py<0||px>=n||py>=m||d[px][py]!=-1||G[px][py]=='#') continue;
if(G[px][py]=='x') d[px][py]=d[x][y]+2;
else d[px][py]=d[x][y]+1;
q.push(node(px,py));
}
}
return -1;
}
void print(){
for(int i=0;i<n;++i){
for(int j=0;j<m;++j)
printf("%02d ",d[i][j]);
printf("\n");
}
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=0;i<n;++i)
scanf("%s",G[i]);
for(int i=0;i<n;++i)
for(int j=0;j<m;++j){
if(G[i][j]=='a') s=node(i,j);
else if(G[i][j]!='r'&&G[i][j]!='a'&&G[i][j]!='.'&&G[i][j]!='#') G[i][j]='x';
}
int ans=bfs();
//print();
if(ans==-1) printf("Poor ANGEL has to stay in the * all his life.\n");
else printf("%d\n",ans);
}
}
如有不当之处欢迎指出！