学步园

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid.
We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

Input

First line contains two integers stand for N and M.

Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.

Process to the end of the file.

Output

For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."

Sample Input

7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

Sample Output

13 

       题目大意就不多说啦，输入文件中包含多个测试数据。每个测试数据的第1 行为两个整数N 和M，接下来有N 行，每行有M 个字符："."代表道路，"a"代表Angel，"r"代表Angel 的朋友，"#"代表墙壁，"x"代表警卫（注意，每个测试数据中字符"a"和"r"均只有一个）。

       具体讲解请看代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN = 1000;
const int INF = 0x7FFFFFFF; // 定义无穷大
struct point
{
    int x;
    int y;
    int time;  // time 为 到达 某点所用时间
};
char map[MAXN][MAXN];
int mint[MAXN][MAXN];  // 记录到达某点的最短时间
queue<point>q;
int X[4]={-1,1,0,0};
int Y[4]={0,0,-1,1};
int n,m;
point start,end;
int bfs()
{
    mint[start.x][start.y] = 0;
    q.push(start);
    point hd,next;
    while (!q.empty())
    {
        hd = q.front();
        q.pop();
        int k ;
        for(k=0;k<4;k++)
        {
            next.x = hd.x+X[k];
            next.y = hd.y+Y[k];
            next.time  = hd.time + 1;
            if(map[next.x][next.y] == 'x')  // 如果遇见警卫，则time 再加 1
            next.time ++; // 注意： 以下是 整个bfs 的核心，从当前位置走到相邻位置(x,y)时，只有当该种走法比之前走到(x,y)位置所花
                        //时间更少，才会把当前走到(x,y)位置所表示的状态入队列，否则是不会入队列的 !!
            if(map[next.x][next.y]!='#' && next.x >= 0 && next.x < n && next.y >= 0 && next.y < m && next.time < mint[next.x][next.y])
            {
                mint[next.x][next.y] = next.time;
                q.push(next);
            }
        }
    }
    return mint[end.x][end.y];
}
int main()
{
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        getchar(); // 吃掉输入第一行末尾的 换行符
        int i,j;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                cin >> map[i][j];
                mint[i][j] = INF; // 所有点的最短时间均初始化为 无穷大 ~
                if(map[i][j] == 'r')
                {
                    start.x = i;
                    start.y = j;
                    start.time = 0; // 把开始时间赋为 0
                }
                else if(map[i][j] == 'a')
                {
                    end.x = i;
                    end.y = j;
                }
            }
            getchar();  // 吃掉每行 末尾的 换行符
        }
        int mintime = bfs();
        if(mintime < INF)
        printf("%d\n",mintime);
        else
        printf("Poor ANGEL has to stay in the prison all his life.\n");

    }
    return 0;
}