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 Q;

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

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

{ {

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

若是所求的目標狀態 if(滿足條件)

跳出循環； return ;

否則 else

從它擴展出子結點，

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

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

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

#include

#include
#include
#include
#include
#include
using namespace std;
const int M=205;
int n,m;
int start_x,end_x;
int start_y,end_y;


char map[M][M];
int cost[M][M];
int fx[4]={1,0,-1,0};
int fy[4]={0,1,0,-1};


typedef struct
{
int x,y;
int time;
}point;


void init()//
{
int i,j;
for(i=0;i for(j=0;j {
if(map[i][j]=='r')// 接入端
{
start_x=i;
start_y=j;
}
if(map[i][j]=='a')//輸出端
{
end_x=i;
end_y=j;
}
cost[i][j]=-1;
}
}


int isvalid(int x,int y)
{
if(x>=0&&x=0&&y return 1;
else
return 0;
}




void BFS()
{
point p1,p2;
queue Q;//定義隊列
int i;

p1.x=start_x;//初始化
p1.y=start_y;
p1.time=0;
cost[p1.x][p1.y]=0;

while(!Q.empty())//初始化
Q.pop();

Q.push(p1);//起始點加入隊列
while(!Q.empty())//當隊列不為空
{
p1=Q.front();//取出隊頭結點信息
Q.pop();

for(i=0;i<4;i++)//滿足條件
{
p2.x=p1.x+fx[i];
p2.y=p1.y+fy[i];
p2.time=p1.time+1;

if(map[p2.x][p2.y]=='#'||!isvalid(p2.x,p2.y))//滿足條件
continue;
if(map[p2.x][p2.y]=='x')
p2.time++;
if(cost[p2.x][p2.y]==-1||p2.time {
Q.push(p2);//入隊
cost[p2.x][p2.y]=p2.time;
}
}
}
}




int main()
{
while(~scanf("%d%d",&n,&m))
{
int i,j;
for(i=0;i scanf("%s",map[i]);

init();
BFS();
if(cost[end_x][end_y]==-1)
printf("Poor ANGEL has to stay in the prison all his life.\n");
else
printf("%d\n",cost[end_x][end_y]);
}
return 0;
}