首页 > 代码库 > 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;}
View Code

 

HDU 1026