新年第一题HDU 1026 ( Ignatius and the Princess I )

从左上角走到右下角，然后把路径打印出来，麻烦就麻烦在打印路径，所幸题目数据小，每个坐标都可以用点一个数表示，一次性胡乱水过，代码比较简单，但是很搓- -、

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#define eps 1e-5
using namespace std;
int n,m;
char g[105][105];
int vis[105][105];
int pre[105105];
char prt[10000][35];
bool flag;
struct node{
    int x,y,step,pre;
    friend bool operator <(node a,node b){
        return a.step>b.step;
    }
};
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int zd(int xx,int yy)
{
    return (xx-1)*m+yy;
}
int zx(int h)
{
    if(h%m==0) return h/m;
    else return h/m+1;
}
int zy(int h)
{
    if(h%m==0) return m;
    else return h%m;
}
void bfs()
{
    priority_queue<node> q;
    while(!q.empty()) q.pop();
    node t;
    t.x=1,t.y=1;
    if(g[1][1]=='.') t.step=0;
    else t.step=g[1][1]-48;//注意起点
    q.push(t);
    vis[t.x][t.y]=1;
    pre[1]=0;
    while(!q.empty())
    {
        node u=q.top();
        q.pop();
        if(u.x==n&&u.y==m) {
            flag=true;
            printf("It takes %d seconds to reach the target position, let me show you the way.\n",u.step);
            int time=u.step;
            int r=0;
            if(g[u.x][u.y]>'0'&&g[u.x][u.y]<='9'){//从终点往前找
                    int we=g[u.x][u.y]-48;
                    while(we--)
                    sprintf(prt[r++],"%ds:FIGHT AT (%d,%d)\n",time--,u.x-1,u.y-1);
                }
            while(pre[zd(u.x,u.y)]!=0){


                int dian=pre[zd(u.x,u.y)];
                sprintf(prt[r++],"%ds:(%d,%d)->(%d,%d)\n",time,zx(dian)-1,zy(dian)-1,u.x-1,u.y-1);

                u.x=zx(dian);
                u.y=zy(dian);

                if(g[u.x][u.y]>'0'&&g[u.x][u.y]<='9'){
                    int we=g[u.x][u.y]-48;
                    while(we--)
                    sprintf(prt[r++],"%ds:FIGHT AT (%d,%d)\n",--time,u.x-1,u.y-1);
                }
                time--;
            }

            for(int i=r-1;i>=0;i--)
                printf("%s",prt[i]);
            break;
        }
        node v=u;
        for(int i=0;i<4;i++)
        {
            v.x=u.x+dx[i];
            v.y=u.y+dy[i];
            if(vis[v.x][v.y]||v.x<1||v.x>n||v.y<1||v.y>m||g[v.x][v.y]=='X') continue;
            if(g[v.x][v.y]=='.') 
                v.step=u.step+1;
            else 
                v.step=u.step+g[v.x][v.y]-'0'+1;
            pre[zd(v.x,v.y)]=zd(u.x,u.y);
            vis[v.x][v.y]=1;
            q.push(v);
        }
    }
    
    if(!flag) printf("God please help our poor hero.\n");
        printf("FINISH\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%s",g[i]+1);
        flag=false;
        memset(vis,0,sizeof vis);
        memset(pre,-1,sizeof pre);
        bfs();
    }
}