在别人的博客上学习了友元函数和进一步理解了优先队列，觉得priority—queue的确很有用。
题解：首先，如果按照题目给的错误暗示从朋友开始寻找angle则会很麻烦，于是用广搜的特性，从angle出发向四处扩展即可，遇到卫兵要加2，但是要注意由于这种广搜并非步数优先，所以我们利用A*搜索的思想，每次取最优的步数的进行搜索。
#include <iostream> #include <cstdio> #include <queue> using namespace std; char map[205][205]; int V[205][205]; int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int n,m; struct node { int x,y; int time; friend bool operator < (const node &a,const node &b) //友元函数 { return a.time>b.time; } }; int go(int x,int y) { if(0<=x&&x<n&&0<=y&&y<m&&map[x][y]!=‘#‘) return 1; return 0; } int bfs(int x,int y) { int i; node start,end; priority_queue<node>Q; memset(V,0,sizeof(V)); start.x=x; start.y=y; start.time=0; V[start.x][start.y]=1; Q.push(start); while(!Q.empty()) { start=Q.top(); Q.pop(); if(map[start.x][start.y]==‘r‘) return start.time; for(i=0;i<4;i++) { end.x=start.x+dir[i][0]; end.y=start.y+dir[i][1]; if(go(end.x,end.y)&&!V[end.x][end.y]) { V[end.x][end.y]=1; if(map[end.x][end.y]==‘x‘) end.time=start.time+2; else end.time=start.time+1; Q.push(end); } } } return -1; } int main() { int i,j; int x,y,ans; 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; }
原文：http://www.cnblogs.com/forever97/p/3541225.html