HDU1242-Rescue

Rescue
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 16313    Accepted Submission(s): 5925

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
 

Author
CHEN, Xue
 

Source
ZOJ Monthly, October 2003
 

题意：
救人，你在r，要救的人在a，'.'是路可以走，'#'是墙，'x'是警卫，走路花费一步，遇见警卫花费两步。
问最小多少步能救人，能的话输出步数，不能的话输出"Poor ANGEL has to stay in the prison all his life."

思路：
搜索题，果断用BFS，要注意的是，深搜回溯太多，效率不高，而简单广搜，入队后每次出队时，根据地
图情况的不同，出队元素所记忆的时间并不是层次递增的，需要全部搜索才能找到正确答案。可以
根据时间进行优先性选择，每次都要出队当前队列中步数最少的出队，而入队处理时，正常处理即可，出队顺序由优先队列自动排序（小记录在前）。这样，我们就可以从“a”进行基于优先队列的范围搜索了，并且在第一
次抵达有朋友的位置时得到正确结果

AC代码：

#include<stdio.h>
#include<string.h>
#include<functional>
#include<queue>
using namespace std;
char a[210][210];
int flag[210][210];
int next[4][2]={
  {-1,0},
  {1,0},
  {0,-1},
  {0,1}
};
int n,m;
struct node
{
   int x,y;
   int step;
   bool operator < (const node &a) const {
        return step>a.step;//最小值优先
    }  

};
void BFS(int x,int y)
{
   priority_queue<node>q;
   node q1,q2;
   int i;
   flag[x][y]=1;
   q1.x=x;q1.y=y;
   q1.step=0;
   q.push(q1);
   while(!q.empty())
   {
      q1=q.top();
      q.pop();
      for(i=0;i<4;i++)
      {
         q2.x=q1.x+next[i][0];
         q2.y=q1.y+next[i][1];
         q2.step=q1.step;
         if(a[q2.x][q2.y]!='#'&&q2.x>=0&&q2.y>=0&&q2.x<n&&q2.y<m)
         {
            if(a[q2.x][q2.y]=='.'&&flag[q2.x][q2.y]==0)
            {
               flag[q2.x][q2.y]=1;
               q2.step+=1;
               q.push(q2);
               continue;
            }

            if(a[q2.x][q2.y]=='x'&&flag[q2.x][q2.y]==0)
            {
               flag[q2.x][q2.y]=1;
               q2.step+=2;
               q.push(q2);
               continue;
            }

            if(a[q2.x][q2.y]=='a')
            {
                printf("%d\n",q2.step+1);
                return;
            }
         }
      }
   }
   printf("Poor ANGEL has to stay in the prison all his life.\n");
}
int main()
{
    int i,j,x,y;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
       memset(a,0,sizeof(a));
       for(i=0;i<n;i++)
       {
          getchar();
          for(j=0;j<m;j++)
          {
             scanf("%c",&a[i][j]);
             if(a[i][j]=='r')
             {
                x=i;y=j;
             }
          }
       }
       memset(flag,0,sizeof(flag));
       BFS(x,y);
    }
    return 0;
}