HDU——1242 Rescue（廣搜）

Rescue

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 21875    Accepted Submission(s): 7792

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

13




///注釋的那幾行代碼是錯誤的，哪位親幫忙看看怎麼回事，那是把'x'也給标記上，改了好久，一直不對

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
#include<algorithm>
#define M(i,n,m) for(int i=n;i<m;i++)
#define N(i,n,m) for(int i=n-1;i>=m;i--)
#define L(N,M) memset(N,M,sizeof(N));
const int INF=210;


using namespace std;


int x0,y0,x1,y1,x2,y2,n,m;
char a[INF][INF];
int b[INF][INF];
int s[4][2]= {{0,-1},{0,1},{-1,0},{1,0}};
bool flag=0;


struct data
{
    int x;
    int y;
    int step;
    bool operator < (const data &a) const
    {
        return a.step<step;
    }
} st,pre;


void bfs()
{
    flag=0;
    L(b,0)
    priority_queue<data>que;
    pre.x=x0;
    pre.y=y0;
    pre.step=0;
    que.push(pre);
    b[x0][y0]=1;
    while(!que.empty())
    {
        st=que.top();
        que.pop();
        M(i,0,4)
        {
            pre=st;
            pre.x+=s[i][0];
            pre.y+=s[i][1];
            if(pre.x>=0&&pre.x<n&&pre.y>=0&&pre.y<m&&!b[pre.x][pre.y]&&a[pre.x][pre.y]!='#')
            {
                if(pre.x==x1&&pre.y==y1)
                {
                    flag=1;
                    pre.step++;
                    printf("%d\n",pre.step);
                    return;
                }
                else
                {
//                    if(pre.x==x2&&pre.y==y2)
                    if(a[pre.x][pre.y]=='x')
                        pre.step++;
                    pre.step++;
                    b[pre.x][pre.y]=1;
                    que.push(pre);
                }


            }
        }
    }
}


int main()
{
    while(~scanf("%d%d",&n,&m))
    {
//        x2=y2=1000000;
        M(i,0,n)
        {
            scanf("%s",a[i]);
            M(j,0,m)
            {
                if(a[i][j]=='a')
                {
                    x0=i;
                    y0=j;
                }
                else if(a[i][j]=='r')
                {
                    x1=i;
                    y1=j;
                }
//                else if(a[i][j]=='x') ///如果說對'x'的位置進行标記的話，就會出錯，我改了好久，一直不對，哪位大神幫忙看看啊，裡面加标記的代碼都是修改後的内容
//                {
//                    x2=i;
//                    y2=j;
//                }
            }
        }
        bfs();
        if(!flag)
            printf("Poor ANGEL has to stay in the prison all his life.\n");
    }
}





///終于明白了，有可能含有多個x，是以這樣标記不可以