本文主要是介绍BFS(搜索) (优先队列 ) HDU1242 Rescue，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题面：
天使被MOLIGPY抓住了！他被Moligpy监禁。监狱被描述为N * M（N，M <= 200）矩阵。监狱里有WALL，ROAD和GUARD。
天使的朋友想要拯救天使。他们的任务是：接近天使。我们假设“接近天使”是为了到达Angel所在的位置。当网格中有一名后卫时，我们必须杀死他（或她？）才能进入网格。我们假设我们向上，向下，向右，向左移动需要1个单位时间，并且杀死一个守卫也需要1个单位时间。我们足够强大，可以杀死所有的守卫。
你必须计算接近天使的最短时间。 （当然，我们只能将UP，DOWN，LEFT和RIGHT移动到绑定范围内的邻居网格。）
输入
第一行包含两个整数代表N和M.
然后是N行，每行有M个字符。 “”代表道路，“a”代表Angel，“r”代表Angel的每个朋友。
处理到文件的末尾。
输出
对于每个测试用例，您的程序应输出一个整数，代表所需的最短时间。如果这样的数字不存在，你应该输出一行包含“贫穷的ANGEL必须一辈子留在监狱里”。
注意是多组输入：
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
const int maxn=250;
using namespace std;
char maze[maxn][maxn];
int vis[maxn][maxn];
int n,m;
int res=-1;
typedef struct node
{int x;int y;int time;bool operator <(const node & b)const{return time>b.time;}
}point;
int a[]={0,0,1,-1};
int b[]={1,-1,0,0};
void bfs(int x,int y,int ox,int oy)
{ priority_queue<point>s;point p;p.x=x;p.y=y;p.time=1;vis[x][y]=1;s.push(p);while(!s.empty()){point t;t=s.top();s.pop();if(t.x==ox&&t.y==oy){res+=t.time;return ;}for(int i=0;i<4;i++){int xx=t.x+a[i];int yy=t.y+b[i];if(xx>=0&&xx<n&&yy>=0&&yy<m&&vis[xx][yy]!=1&&maze[xx][yy]!='#'){point q;q.x=xx;q.y=yy;if(maze[xx][yy]=='x')q.time=t.time+2;elseq.time=t.time+1;s.push(q);vis[xx][yy]=1;} } }
}
int main()
{int i,j;int sx,sy;int ex,ey;while(cin>>n>>m){memset(vis,0,sizeof(vis));res=-1;for(i=0;i<n;i++)for(j=0;j<m;j++){cin>>maze[i][j];if(maze[i][j]=='r'){sx=i;sy=j;}if(maze[i][j]=='a'){ex=i;ey=j;}}bfs(sx,sy,ex,ey);if(res==-1)cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;elsecout<<res<<endl; } return 0;
}这道题 ，如果不考虑士兵的话，（因为题数据问题），交一发纯BFS 求最短距离，就可以 AC。但是 ，不是总是数据有问题，这道题需要判断 需要过士兵，还是不过士兵，因为过士兵要 耗时 2个单位，如果绕过的话，可能会有更好的路线 ，说这就需要判断，我们就可以交给优先队列，按 时间 从小到大来排列。到时候，就会优先走时间少的路线，直到 a 天使处。
很好的思路，优先队列 + BFS 。
这篇关于BFS(搜索) (优先队列 ) HDU1242 Rescue的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
