首页 > 代码库 > HDU 1026
HDU 1026
http://acm.hdu.edu.cn/showproblem.php?pid=1026
记录bfs路径,用一个数组记录next前驱的方向,然后递归的时候减回去即可
#include <iostream>#include <cstdio>#include <cstring>#include <queue>using namespace std ;const int INF=0xfffffff;int n,m;char M[105][105];struct node{ int x,y,step; friend bool operator <(node a,node b){ return a.step>b.step; }};int dx[]={1,-1,0,0};int dy[]={0,0,1,-1};int vis[105][105];int rd[105][105];int bfs(){ memset(vis,0,sizeof(vis)); priority_queue <node> q; node s; s.x=0;s.y=0;s.step=0; if(M[0][0]!=‘X‘ && M[n-1][m-1]!=‘X‘)q.push(s); while(!q.empty()){ node u=q.top(); q.pop(); if(u.x==n-1 && u.y==m-1)return u.step; for(int i=0;i<4;i++){ int xx=u.x+dx[i]; int yy=u.y+dy[i]; if(xx<0 || xx>=n || yy<0 || yy>=m)continue; if(M[xx][yy]==‘X‘)continue; if(vis[xx][yy])continue; vis[xx][yy]=1; node next=u; next.x=xx;next.y=yy;next.step++; if(M[xx][yy]>=‘1‘ && M[xx][yy]<=‘9‘) next.step+=(M[xx][yy]-‘0‘); rd[xx][yy]=i; q.push(next); } } return INF;}int tt;void output(int x,int y){ if(rd[x][y]==-1)return; int xx=x-dx[rd[x][y]]; int yy=y-dy[rd[x][y]]; output(xx,yy); printf("%ds:(%d,%d)->(%d,%d)\n",tt++,xx,yy,x,y); if(M[x][y]>=‘1‘ && M[x][y]<=‘9‘){ int nn=M[x][y]-‘0‘; while(nn--){ printf("%ds:FIGHT AT (%d,%d)\n",tt++,x,y); } }}int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=0;i<n;i++) scanf("%s",M[i]); int ans=bfs(); if(ans==INF)puts("God please help our poor hero."); else{ printf("It takes %d seconds to reach the target position, let me show you the way.\n",ans); rd[0][0]=-1; tt=1; output(n-1,m-1); } puts("FINISH"); } return 0;}
HDU 1026
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。