hdu1242 优先队列 以及非优先队列2中做法

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

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
 
/*题目大意：
在一个n×m的地图上，有一个a,和一些r。＃表示墙，.表示路。
x表示有一个守卫。r可以上下左右移动，每次只能移动一个点，需要1的时间。如果移到
x的位置，需要额外1的时间杀掉x。求所有r最早到a的最小时间
解题思路：用优先队列优化不等价的移动。每次获得的是具有最优值的时间。


下面是非优先队列 居然AC了 哈哈 太搞笑了 为了这个题 我辛辛苦苦的搞了一天的优先队列 谁知道把前天写的程序拿出来重新修改了下 过了 嘿嘿 给力啊 
不过还是要写个优先队列的 这样可以节省大量的时间
#include<stdio.h>
#include<string.h>
int a[205][205],s_x,s_y,e_x,e_y,flag[205][205];
int b[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
struct haha
{
int x;
int y;
int ti;
}que[1000000];
int bfs()
{
 int head=0,tail=1,min=100000000,i;
 que[1].x=s_x;que[1].y=s_y;que[1].ti=0;flag[s_x][s_y]=1;
 while(head<tail)
 {
 head++;
 if(que[head].ti>min) continue;
 if(que[head].x==e_x&&que[head].y==e_y)
 {
 if(min>que[head].ti) min=que[head].ti;continue;
 } 
 for(i=0;i<4;i++)
 if(a[que[head].x+b[i][0]][que[head].y+b[i][1]]!=0&&flag[que[head].x+b[i][0]][que[head].y+b[i][1]]==0)
 {
 flag[que[head].x+b[i][0]][que[head].y+b[i][1]]=1;
 que[++tail].x=que[head].x+b[i][0];
 que[tail].y=que[head].y+b[i][1];
 que[tail].ti=que[head].ti+a[que[head].x+b[i][0]][que[head].y+b[i][1]];
 }
 }
return min; 
}
int main()
{
int hang,lie,i,j,ch,ans;
while(scanf("%d %d",&hang,&lie)!=EOF)
{
getchar();
memset(a,0,sizeof(a));
memset(flag,0,sizeof(flag));
for(i=1;i<=hang;i++)
{
for(j=1;j<=lie;j++)
{
ch=getchar();
if(ch=='#') a[i][j]=0;
if(ch=='.') a[i][j]=1;
if(ch=='x') a[i][j]=2;
if(ch=='a'){s_x=i;s_y=j;a[i][j]=1;}
if(ch=='r'){e_x=i;e_y=j;a[i][j]=1;}
}
 getchar();
}
ans=bfs();
if(ans==100000000) printf("Poor ANGEL has to stay in the prison all his life.\n");
else 
 printf("%d\n",ans);
}
}



下面是优先队列版本
：
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int a[205][205],e_x,e_y;
int b[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
struct haha
{
int x;
int y;
int ti;
bool operator <(const haha &a) const //a是随意定的名字 就用来当做一个结构体的节点
{
return ti>a.ti;//注意对于结构体的优先队列要把自定义函数放进结构体内才行 >使得小的先出<使得大的先出
}
}q,temp,end;
priority_queue<haha>duilie;//定义队列 duilie是随便取的名字
int bfs()
{
 int i;
 int tx,ty;
 while(!duilie.empty())
 {
 temp=duilie.top();
 duilie.pop();
 for(i=0;i<4;i++)
 {
 tx=temp.x+b[i][0];
 ty=temp.y+b[i][1];
 if(a[tx][ty]!=0)
 {
 q.x=tx;
 q.y=ty;
 q.ti=temp.ti+a[tx][ty];
 duilie.push(q);
 if(tx==e_x&&ty==e_y) return temp.ti+1;
 a[tx][ty]=0;
 }
 }
 }
 return -1;
}
int main()
{
int hang,lie,i,j,ch,ans;
while(scanf("%d %d",&hang,&lie)!=EOF)
{
getchar();
memset(a,0,sizeof(a));
 while(!duilie.empty())
 duilie.pop();
 
for(i=1;i<=hang;i++)
{
for(j=1;j<=lie;j++)
{
ch=getchar();
if(ch=='#') a[i][j]=0;
if(ch=='.') a[i][j]=1;
if(ch=='x') a[i][j]=2;
if(ch=='a')
{
 q.x=i;
q.y=j;
q.ti=0;
duilie.push(q);
a[i][j]=1;
}
if(ch=='r'){e_x=i;e_y=j;a[i][j]=1;}
}
 getchar();
}
ans=bfs();
if(ans==-1) printf("Poor ANGEL has to stay in the prison all his life.\n");
else 
 printf("%d\n",ans);
}
return 0;
}