hdu 1242 Rescue (BFS+优先队列)
题意
一个地图中，给定起点和终点，上下左右走，每走一步花1个单位时间，遇到怪，需要杀死怪，额外花1个单位时间，求从起点到终点最少花多少分钟。
解题思路：
主要思路是广度优先搜索，但因为其中有怪，需要额外花时间，那么对于队列里面的每个节点（保存x,y坐标和当前所用时间)，要想最少花时间，那么每次在队头取出的元素应该是队列里面所用时间最少的，所以应该用优先队列。
（我最开始就就是一直没有优先队列，就一直答案不太对,看了别人的代码才用最优队列，才过）
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int n,m,x,y;
char mi[205][205];//地图
int flag[205][205];//标记
int zou[4][2]={
{
1,0},{
-1,0},{
0,1},{
0,-1}};
struct node{
int x,y,step;bool operator < (const node &a) const {
//每次求出最优的路线，最少的步数先执行return step>a.step; }
};
void bfs(int x,int y){
//最优队列priority_queue<node>q;node q1,q2;flag[x][y]=1;q1.x=x;q1.y=y;q1.step=0;q.push(q1);while(!q.empty()){
q1=q.top();q.pop();//printf("%d %d %d\n",q1.x,q1.y,q1.step);for(int i=0;i<4;i++){
q2.x=q1.x+zou[i][0];q2.y=q1.y+zou[i][1];q2.step=q1.step;if(mi[q2.x][q2.y]!='#'&&q2.x>0&&q2.x<=n&&q2.y>0&&q2.y<=m&&flag[q2.x][q2.y]==0){
if(mi[q2.x][q2.y]=='.'){
q2.step+=1;flag[q2.x][q2.y]=1;q.push(q2);continue;}if(mi[q2.x][q2.y]=='x'){
q2.step+=2;flag[q2.x][q2.y]=1;q.push(q2);continue;}if(mi[q2.x][q2.y]=='a'){
printf("%d\n",q2.step+1);return ;}} }}printf("Poor ANGEL has to stay in the prison all his life.\n");
}
int main(int argc, char** argv) {
while(scanf("%d %d",&n,&m)!=EOF){
memset(mi,0,sizeof(mi));for(int i=1;i<=n;i++){
getchar();for(int j=1;j<=m;j++){
scanf("%c",&mi[i][j]);if(mi[i][j]=='r'){
x=i;y=j;}}}memset(flag,0,sizeof(flag));bfs(x,y);}return 0;
}
补充知识：
优先队列(priority_queue)的基本操作：
empty();队列为空返回1
pop();出队
push();入队
top();返回队列中优先级最高的元素
size();返回队列中元素的个数