hdu2425解题报告

发布时间:2017-2-22 18:45:21 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu2425解题报告",主要涉及到hdu2425解题报告方面的内容,对于hdu2425解题报告感兴趣的同学可以参考一下。

题意很明了,就是找起点到终点的最短用时,但是因为每种不同的地带,用时不同,那么这里可以用到优先队列,来处理总共用时,我们每次总是把用时最短的坐标点出队,访问四周,那么,就总能选择用时最短的去走,直到达到目的地: 上马: 0MS 244K #include<cstdio> #include<queue> using namespace std; #define MAX 22 struct node { int x,y,time;//坐标,以及起点到此点的用时 bool operator <(const node &N)const//用优先队列,按用时从小到大排序 { return N.time<time; } }st;//开始点 int R,C;//行列 int endx,endy;//目标的坐标 char map[MAX][MAX]; int T[3];//对于三种不同地带的用时 void Input() { int i; scanf("%d%d%d",&T[0],&T[1],&T[2]); for(i=0;i<R;i++,getchar()) scanf("%s",map[i]); scanf("%d%d%d%d",&st.x,&st.y,&endx,&endy); st.time=0; } int vis[4][2]={{-1,0},{1,0},{0,1},{0,-1}}; int bfs() { priority_queue<node>q; map[st.x][st.y]='@';//走过了的地方我们就标记为石头,不再走 q.push(st); while(!q.empty()) { node pre=q.top();q.pop(); if(pre.x==endx && pre.y==endy) { return pre.time; } for(int i=0;i<4;i++) { node p; p.x=pre.x+vis[i][0]; p.y=pre.y+vis[i][1]; p.time=pre.time; if(p.x>=0 && p.y >= 0 && p.x < R && p.y < C && map[p.x][p.y]!='@')//对于地图中不是石头的地方访问 { if(map[p.x][p.y]=='T')p.time+=T[2];//这里看看是哪一种地带, else if(map[p.x][p.y]=='.')p.time+=T[1]; else if(map[p.x][p.y]=='#')p.time+=T[0]; map[p.x][p.y]='@'; q.push(p); } } } return -1;//走不到返回-1 } int main() { int cas=1; while(~scanf("%d%d",&R,&C)) { Input(); printf("Case %d: %d\n",cas++,bfs()); } return 0; }个人愚昧观点,欢迎指正和交流

上一篇:[置顶] OGG同构(ORACLE-ORACLE)、异构(ORACLE-MYSQL)同步配置及错误解析
下一篇:黑马程序员_JAVA笔记03——循环语句与函数

相关文章

相关评论