1242 Rescue【bfs】

Rescue

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

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
        

找最短路徑，bfs 題型，因為中間過程可能會影響時間的使用不均衡，是以這個題要用優先隊列來解決，優先考慮用時間少的方法，把每一個狀态拓展來的狀态都放進隊列裡，注意标記重複的狀态.....從天使的位置開始考慮比較好，因為 r 可能有多個，隻需要找到最近的那個 r 就行！！

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
char x[205][205];
int v[205][205],n,m,kase;
int fx[4]={-1,0,0,1},fy[4]={0,-1,1,0};
struct save
{
    int x,y,t;
    friend bool operator<(save a,save b)
    {
        return a.t>b.t;//時間少的優先考慮
    }
}r,t;
priority_queue<save> q;
void bfs()
{
    while(!q.empty())
    {
        r=q.top();
        q.pop();
        if(x[r.x][r.y]=='r')//找到了一個，立刻終止
        {
            kase=1;
            return;
        }
        for(int i=0;i<4;++i)//向四個方向拓展
        {
            int tx=fx[i]+r.x,ty=fy[i]+r.y;
            t.x=tx; t.y=ty; t.t=r.t+1;
            if(x[tx][ty]=='#')
            {
                continue;
            }
            if(x[tx][ty]=='x')//有守衛，多費一個時間
            {
                ++t.t;
            }
            if(tx>=0&&tx<n && ty>=0&&ty<m&&!v[tx][ty])
            {
                v[tx][ty]=1;//用過的标記
                q.push(t);
            }
        }
    }
}
int main()
{
    int i,j,a,b;char y;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=0;i<n;++i)
        {
            getchar();
            for(j=0;j<m;++j)
            {
                scanf("%c",&y);
                x[i][j]=y;
                if(y=='a')
                {
                    a=i;b=j;
                }
            }
        }
        while(!q.empty())//注意清空
        {
            q.pop();
        }
        memset(v,0,sizeof(v));
        kase=0;
        r.x=a; r.y=b; r.t=0;
        q.push(r);v[a][b]=1;//把狀态入隊列....
        bfs();
        if(kase==1)
        {
            printf("%d\n",r.t);
            continue;
        }
        printf("Poor ANGEL has to stay in the prison all his life.\n");
    }
    return 0;
}