Rescue BFS+优先队列 杭电1242

 

思路 ： 优先队列
每次都取最小的时间，遇到了终点直接就输出

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=200;
int n,m,sa,ea,sr,er;
char arr[N][N];
int bb[N][N]={0};
struct stu{
int a,b;
int time;
bool friend operator <(const stu &a,const stu &b){
return a.time>b.time;
}
};
int a[4]={0,1,0,-1};
int br[4]={1,0,-1,0};
void bfs(){
priority_queue<stu>que;
stu s;
s.a=sa;
s.b=ea;
s.time=0;
que.push(s);
bb[sa][ea]=1;
int flag=0;
while(que.size()){
stu p;
p=que.top();
que.pop();
stu st;
for(int i=0;i<4;i++){
st.a=p.a+a[i];
st.b=p.b+br[i];
if(st.a>=0&&st.b>=0&&st.a<n&&st.b<m&&bb[st.a][st.b]!=1&&arr[st.a][st.b]!='#'){
bb[st.a][st.b]=1;
if(arr[st.a][st.b]=='x')
st.time=p.time+2;
else {
st.time=p.time+1;
}
que.push(st);
if(st.a==sr&&st.b==er)
{
cout<<st.time<<endl;
return ;
}
}
}
}
cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
return ;
}
int main()
{
while(cin>>n>>m){
memset(bb,0,sizeof(bb));
for(int i=0;i<n;i++)
scanf("%s",&arr[i]);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
{
if(arr[i][j]=='a'){
sa=i;
ea=j;
}
else if(arr[i][j]=='r'){
sr=i;
er=j;
}
}
}
bfs();
}
return 0;
}