hdoj 1242 Rescue (BFS)

Rescue

http://acm.hdu.edu.cn/showproblem.php?pid=1242

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

Total Submission(s): 18962    Accepted Submission(s): 6771

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  

Recommend Eddy   |   We have carefully selected several similar problems for you:  1240 1016 1010 1072 1253    第一次寫 BFS 

題目大意：

 1.在含有障礙的迷宮中求從一點到一點的最短時間或步數，

 2.這個題目中，天使的朋友不止一個，是以搜尋的起點應該是從天使開始搜到朋友為止，

 3.題目求的是最短時間，是以應該才用優先隊列，小步數優先。

----------------------------------------------------------------------------------------------------------------------------------------

BFS：

1.從圖中的某一項V0開始，先通路V0;

2.通路所有與v0相鄰接的頂點 v1、v2、、、、、、Vt;

3.依次通路與 v1、v2、、、、、、Vt 相鄰接的所有未曾通路過的頂點;

4.循此以往，直至所有的頂點都被通路過為止；

BFS具體操作：

      定義一個隊列；          queue<node> Q;

     起始點加入隊列；       Q.push(p);

    while(隊列不空)            while(!Q.empty())

   {                                        {

      取出隊頭結點；             p=Q.front； Q.pop；

     若是所求的目标狀态      if(滿足條件)

          跳出循環；                        return ; 

    否則                                   else

        從它擴充出子結點，      

        全部添加到隊尾中               Q.push();

   }                                         }

若循環中找到目标，輸出結果；否則，輸出無解；

----------------------------------------------------------------------------------------------------------------------------------------

#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define MAX 205
char map[MAX][MAX];
int step[MAX][MAX];

int f[2][4]={1,0,-1,0,0,1,0,-1};
int n,m; 	
int sx,sy,ex,ey;
struct node
{
	int x;
	int y;
	int time;
};

queue<node>q;
void input()
{
	for(int i=0;i<n;i++)
	 for(int j=0;j<m;j++)
	 {
	 	if(map[i][j]=='r')//朋友
	 	{
	 	 sx=i;
		 sy=j;	
		}
		if(map[i][j]=='a')//天使
		{
		  ex=i;
		  ey=j;
		}
		step[i][j]=-1;
	 }
}

void BFS()
{
	node p1,p2;
	p1.x=sx;
	p1.y=sy;
	p1.time=0;
	step[p1.x][p1.y]=0;
	
	while(!q.empty())
	q.pop();
	
	q.push(p1);
	while(!q.empty())
    {
      p1=q.front();
      q.pop();
      
      for(int i=0;i<4;i++)
      {
      	p2.x=p1.x+f[0][i];
      	p2.y=p1.y+f[1][i];
      	
      	if(map[p2.x][p2.y]!='#'&&(p2.x>=0&&p2.x<n&&p2.y>=0&&p2.y<m))//邊界
      	{
      	          p2.time=p1.time+1;//行走一步需要1s
		  if(map[p2.x][p2.y]=='x')//殺一個守衛需要1s
		  p2.time++;
		  if(step[p2.x][p2.y]==-1||p2.time<step[p2.x][p2.y])
		  {
			q.push(p2);
			step[p2.x][p2.y]=p2.time; 
		  }	
		}
	  }
	}
}
int main()
{
   while(~scanf("%d%d",&n,&m))
   {
   	for(int i=0;i<n;i++)
   	scanf("%s",map[i]);
   	input();
   	BFS();
   	if(step[ex][ey]==-1)
   	printf("Poor ANGEL has to stay in the prison all his life.\n");
   	else
   	printf("%d\n",step[ex][ey]);
   }
   return 0;
}