## 优先队列广搜 hdu 1242 原

洛伊佩拉

Rescue
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``

code:

``````#include <iostream>
#include "stdio.h"
#include "queue.h"
#include "memory.h"

char map[205][205];            //图的定义
char vit[205][205];            //图访问的判断

int fangxiang[4][2]={1,0,-1,0,0,1,0,-1};
using namespace std;

struct point
{
int x;
int y;
int step;
friend bool operator<(point n1,point n2)
{
return n2.step<n1.step;
}
};
int n,m;            //图的长宽
point end;

priority_queue <point> q;  //定义一个优先队列
void bfs(void)
{

point cut;
while(!q.empty())        //队列不为空
{
cut=q.top();
q.pop();
vit[cut.x][cut.y]=1;    //该位置访问过

if(cut.x==end.x&&cut.y==end.y)
{
end.step=cut.step;
return;
}

int newx,newy;        //新坐标
int i;
for(i=0;i<4;i++)
{
newx=cut.x+fangxiang[i][0];
newy=cut.y+fangxiang[i][1];
if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&!vit[newx][newy]&&(map[newx][newy]=='.'||map[newx][newy]=='x'||map[newx][newy]=='a'))        //满足条件
{
point feature;        //可行点
feature.x=newx;
feature.y=newy;
vit[newx][newy]=1;
if(map[newx][newy]=='x')            //有警卫
{
feature.step=cut.step+2;
}else
{
feature.step=cut.step+1;
}
//    printf("x=%d,y=%d,step=%d\n",newx,newy,feature.step);
q.push(feature);

}

}

}
}

int main(int argc, char *argv[])
{

while(scanf("%d%d",&n,&m)!=EOF)
{

int i,j;
point start;
while(!q.empty())        //队列清空
{
q.pop();
}
memset(vit,0,sizeof(vit));
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>map[i][j];
if(map[i][j]=='r')    //找到起点
{
start.x=i;
start.y=j;
start.step=0;
}
if(map[i][j]=='a')    //找到终点
{
end.x=i;
end.y=j;
end.step=-1;
}
}
}

q.push(start);
bfs();            //开始广度搜索

if(end.step!=-1)
{
printf("%d\n",end.step);
}else
{
printf("Poor ANGEL has to stay in the prison all his life.\n");
}

}
return 0;
}``````

### 洛伊佩拉

Dear_Jia
2017/11/16
0
0

datacube
2016/06/18
39
0
【算法系列 三】 Quene

Hosee
2016/03/01
102
0

Wenson_Jay
07/22
0
0
HDU 3085 Nightmare Ⅱ

Nightmare Ⅱ 　　Last night, little erriyue had a horrible nightmare. He dreamed that he and his girl friend were trapped in a big maze separately. More terribly, there are two......

suvvm
2018/12/05
0
0

19.1 Linux监控平台介绍 19.2 zabbix监控介绍 19.3/19.4/19.6 安装zabbix 19.5 忘记Admin密码如何做 19.1 Linux监控平台介绍： 常见开源监控软件 ~1.cacti、nagios、zabbix、smokeping、ope...

oschina130111

13
0

7
0
DNS-over-HTTPS 的下一代是 DNS ON BLOCKCHAIN

10
0
CC攻击带来的危害我们该如何防御？

12
0

8
0