题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1242
题目大意：给出一张图，其中#代表墙，.代表路，r是Angel的朋友所在的位置，而a代表Angel所在的位置，朋友们要到达Angel所在的位置才能救他，求从朋友到Angel最短的路线，若有最短路线，则输出路线长度，否则输出Poor ANGEL has to stay in the prison all his life.
解题思路：简单的搜索问题，深搜和广搜都可以解决
AC代码：
//方法一：dfs
#include <iostream>
#include <cstring>
using namespace std;
int dir[4][2]={0,-1,-1,0,0,1,1,0};
char graph[205][205];
bool visit[205][205];
int n,m;
int minlen;
void dfs(int a,int b,int len)
{if(graph[a][b]=='r'){if(len<minlen)minlen = len;return;}if(graph[a][b]=='x')len++;for(int i=0;i<4;i++){int aa = a+dir[i][0];int bb = b+dir[i][1];if(aa>=0&&aa<n&&bb>=0&&bb<m&&!visit[aa][bb]&&graph[aa][bb]!='#'){visit[aa][bb] = 1;dfs(aa,bb,len+1);visit[aa][bb] = 0;}}
}
int main()
{int x,y;while(cin>>n>>m){for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>graph[i][j];if(graph[i][j]=='a'){x = i;y = j;}}}memset(visit,0,sizeof(visit));minlen = 20000;dfs(x,y,0);if(minlen!=20000)cout<<minlen<<endl;else cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;}return 0;
}
//方法二：bfs
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
char graph[205][205];
int visit[205][205];
int dir[4][2] = {-1,0,0,-1,1,0,0,1};
int x1,y1,x2,y2;
int n,m;
struct Node{int x;int y;int step;friend bool operator <(Node a,Node b){return b.step<a.step;}
};
bool check(int x,int y)
{if(x<0||y<0||x>=n||y>=m||!visit[x][y]||graph[x][y]=='#')return true;return false;
}
int bfs()
{priority_queue<Node> q;Node start;start.x = x1;start.y = y1;start.step = 0;q.push(start);visit[x1][y1] = 0;while(!q.empty()){start = q.top();Node next;q.pop();if(start.x==x2&&start.y==y2)return start.step;for(int i=0;i<4;i++){next = start;next.x += dir[i][0];next.y += dir[i][1];if(check(next.x,next.y))continue;next.step++;if(graph[next.x][next.y]=='x')next.step++;if(visit[next.x][next.y]>=next.step){visit[next.x][next.y] = next.step;q.push(next);}}}return 0;
}
int main()
{while(cin>>n>>m){memset(visit,1,sizeof(visit));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>graph[i][j];if(graph[i][j]=='r'){x1 = i;y1 = j;}if(graph[i][j]=='a'){x2 = i;y2 = j;}}}int result = bfs();if(result)cout<<result<<endl;else cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;}return 0;
}