题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1242
题意：天使被困在监狱，他的朋友们想见他，监狱的地形复杂，包括路(用点标示),墙(用#标示)，天使的位置（用a标示），他的朋友(用r标示),监狱里还有守卫(用x标示),他的朋友只能向左右上下四个方向走，走以不花一单位时间，若碰上守卫，消灭守卫需要额外花费一单位时间。问最少多长时间天使能见到他的朋友。
分析：终点‘a’只有一个，但是起点‘r’可能有很多个，想想直接搜不容易，就反过来把终点当作起点，这样只需要找到一条最近的就可以了。普通队列过不了的直接上优先队列即可。
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=250; char a[maxn][maxn]; int vis[maxn][maxn]; int dir[4][2]= {1,0,-1,0,0,1,0,-1}; //方向数组 int n,m,countt=0; struct node { int x;//x，y坐标，step记录一个前驱 int y; int step; }; int bfs(int x,int y) { node now,next; queue<node>q; now.x=x; now.y=y; now.step=0; q.push(now); while(!q.empty()) { now=q.front(); q.pop(); if(a[now.x][now.y]=='r') { countt=now.step; return countt; } for(int i=0; i<4; i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&a[next.x][next.y]!='#'&&vis[next.x][next.y]==0) { vis[next.x][next.y]=1; next.step=now.step+1;//该路径上合法点每一步加1 if(a[next.x][next.y]=='x')//该条路上有守卫步数加1 { a[next.x][next.y]='.'; next.step++; } q.push(next); } } } return -1; } int main() { while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; memset(vis,0,sizeof(vis)); for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin>>a[i][j]; } } int num1,num2; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(a[i][j]=='a') { num1=i; num2=j; } } } int min_sum=0; min_sum=bfs(num1,num2); if(min_sum==-1) printf("Poor ANGEL has to stay in the prison all his life.\n"); else printf("%d\n",min_sum); } return 0; }
