本文主要是介绍hdu1242，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：点击打开链接
题意：r为起点，a为终点，没走一步需要花费一个单位时间，x为怪，遇到怪可以考虑打怪，打怪会花费一个单位时间，问走到终点最少花费时间为多少
代码：
#include <queue>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int n,m,enx,eny;
int xx[]={-1,0,1,0};
int yy[]={0,-1,0,1};
char s[205][205];
struct node{int x,y,sum;
};
struct cmp{bool operator()(node a,node b){return a.sum>b.sum;}
};
int bfs(node st){priority_queue<node,vector<node>,cmp>q; //时间最少要用优先队列node cur,temp;int i,j;q.push(st);while(q.size()){cur=q.top();q.pop();if(cur.x==enx&&cur.y==eny) //这里要用坐标，因为所有走过的路都变为了# return cur.sum;for(i=0;i<4;i++){temp.x=cur.x+xx[i];temp.y=cur.y+yy[i];if(temp.x>=1&&temp.x<=n&&temp.y>=1&&temp.y<=m)if(s[temp.x][temp.y]!='#'){if(s[temp.x][temp.y]=='.')temp.sum=cur.sum+1;else if(s[temp.x][temp.y]=='x')temp.sum=cur.sum+2;q.push(temp);s[temp.x][temp.y]='#'; //走过的就变为#}}}return 0;
} //bfs模板
int main(){int i,j,ans;node st;while(cin>>n>>m){for(i=1;i<=n;i++)for(j=1;j<=m;j++){cin>>s[i][j];if(s[i][j]=='r')st.x=i,st.y=j,st.sum=0;if(s[i][j]=='a')enx=i,eny=j;}ans=bfs(st);if(ans!=0)printf("%d\n",ans);elseprintf("Poor ANGEL has to stay in the prison all his life.\n");}return 0;
}
这篇关于hdu1242的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
