Rescue

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15884 Accepted Submission(s): 5759

Problem Description

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

大意：天使 a被关朋友r(可以有多个)要去救天使 r要绕过#（障碍物）和x（守卫）去寻找天使a 不能穿过障碍物要走守卫那一步必须打败守卫时间为2，其他每步时间为1；

问找到天使的最短时间；

思路：用搜索做，由于r可以有多个，所以从天使a出发，每次都有四个方向可以走用visit[x][y]记录该点是否被走过，如往一个方向走但是另一个点被visit过就不会重复走了

往其中一个方向走后继续进行dfs直到找到r或者无路可走注意由于是探索性的走，走完进行DFS后记得往后退，状态还原；

代码如下：

#include<iostream>
using namespace std;
#include<string.h>
#define max 205
char map[max][max];
long a[100000],step,sum,n,m,visited[max][max];
long directions[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

//DFS 不用队列，不用结构体
/*
 *
 7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........ output<<13
 */
void DFS(int x,int y)
{
    int i,mx,my;

    if(map[x][y]=='r')
        a[sum++]=step;

    else if(map[x][y]!='#')
    {

        for(i=0;i<4;i++)
        {
            mx=x+directions[i][0];
            my=y+directions[i][1];


            if(map[mx][my]!='#'&&mx>=1&&mx<=n&&my>=1&&my<=m&&!visited[mx][my])//不是墙并且没走过
            {
                if(map[x][y]=='x')
                    step++;
                step++;
                visited[mx][my]=1;

               DFS(mx,my); //所以关键要得到值的是递归的这一步  推导的时候让这个的下一个DFS就是到达朋友那点比较好理解为什么后面要还原

                visited[mx][my]=0;//这一步的原因，上面DFS进行完后要将状态还原
                step--;           //下面这些都要还原
                if(map[x][y]=='x')
                    step--;


            }
        }
    }
}




int main()
{

    long i,j,x,y,min;
    while(cin>>n>>m)
    {

        memset(visited,0,sizeof(visited));
        sum=0;
        step=0;
        min=max;

        for(i=1;i<=n;i++)
        {
            
            for(j=1;j<=m;j++)
            {
                cin>>map[i][j];
                if(map[i][j]=='a')//记录天使的地址
                {
                    x=i;
                    y=j;
                }
            }
        }

        visited[x][y]=1;
        DFS(x,y);

        if(sum==0)
            cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
        else
        {
            for(i=0;i<sum;i++)
                if(a[i]<min)
                    min=a[i];
            cout<<min<<endl;

        }

    }
    return 0;
}

today lazy . tomorrow die .