hdu 杭电 1242 Rescue

题意：从a开始，找到r所需的时间（r可以有多个，找到第一个输出所需的时间即可），‘#’是墙不可走，

      经过‘.’时间加1，经过‘x’时间加2.

 

解法：广搜，使用优先队列，队列中的首元素都为队列中step最小的一个元素。

 

注意：r可以有多个。

 

ac代码：

#include<iostream>
#include<queue>
using namespace std;
const int M=200+10;
char map[M][M];//地图
int use[M][M];//用作标记
int nn[4][2]={0,1,-1,0,0,-1,1,0};//方向向量：左，上，右，下
struct node
{
int i;
int j;
int step;
const bool operator <(const node &old)const//使用优先队列，此处重载小于号

{
return step>old.step;//队列中的元素按setp的值升序排列

}
};
int
outside(int x,int y,int n,int m)//判断是否出界
{
if(x>0&&x<=n&&y>0&&y<=m)
return 1;
return 0;
}
int main()
{
struct node temp;
priority_queue<struct node> q;
int n,m;
while(cin>>n>>m)
{
memset(use,0,sizeof(use));
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>map[i][j];
if(map[i][j]=='a')
{
temp.i=i;
temp.j=j;
temp.step=0;
}
}
}
q.push(temp);
map[temp.i][temp.j]='#';
int foat=1;
while(!q.empty()&&foat)
{
for(i=0;i<4;i++)
{
temp.i=q.top().i+nn[i][0];
temp.j=q.top().j+nn[i][1];
if(outside(temp.i,temp.j,n,m)&&map[temp.i][temp.j]!='#')
{
if(map[temp.i][temp.j]=='x')
temp.step=q.top().step+2;
else
temp.step=q.top().step+1;
q.push(temp);
if(map[temp.i][temp.j]=='r')
{
foat=0;
break;
}
map[temp.i][temp.j]='#';
}
}
q.pop();
}
if(!foat)
cout<<temp.step<<endl;
else
cout<<"Poor ANGEL has to stay in the prison all his life." <<endl;
while(!q.empty())
q.pop();
}
return 0;
}
峰注：不明白请留言。