本文主要是介绍hdu 1242 Rescue(BFS+优先队列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
起初只是用DFS做，但后来发现问题太多了，起点是一个，但可能有多个士兵，要找到最小的距离即要求每一个子问题的结果都是最小值。用深度优先搜索自然不能每次都返回较小值。而广度优先搜索就像使用了分身术一样，4个方向都有friend去找angel，各自返回自己的最小值，所以思路就是BFS+优先队列。
<pre name="code" class="cpp"><pre name="code" class="cpp">#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
char imap[211][211];
int n,m,x_s,y_s,x_e,y_e;
struct node
{int x,y,step;friend bool operator<(node n1,node n2) // 不能是 bool operator<(node n1,node n2)哦{return n2.step<n1.step;}
};
int dir[4][2]={1,0, -1,0, 0,1, 0,-1}; //不用{{}，{}……}
int judge(int x,int y)
{if(x>=0&&x<n&&y>=0&&y<m&&imap[x][y]!='#')return 1;return 0;
}
int BFS(){priority_queue<node>q;node cur,next;int i;cur.x=x_s;cur.y=y_s;cur.step=0;imap[cur.x][cur.y]='#';q.push(cur);while(!q.empty()){cur=q.top();q.pop();if(cur.x==x_e && cur.y==y_e) return cur.step; //返回最小值for(i=0;i<4;i++){next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];if(!judge(next.x,next.y)) continue;if(imap[next.x][next.y]=='x') next.step=cur.step+2;else next.step=cur.step+1;imap[next.x][next.y]='#';q.push(next);}//cout<<q.top().x<<" "<<q.top().y<<endl;}return -1;
}
int main()
{//freopen("cin.txt","r",stdin);int ans;int i,j;while(~scanf("%d%d",&n,&m)){memset(imap,0,sizeof(imap));getchar();for(i=0;i<n;i++){for(j=0;j<m;j++){scanf("%c",&imap[i][j]);if(imap[i][j]=='r'){ x_s=i; y_s=j; }else if(imap[i][j]=='a'){ x_e=i; y_e=j; }}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;
}
这篇关于hdu 1242 Rescue(BFS+优先队列)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
