Hdu 1026 Ignatius and the Princess I (BFS 优先队列+路径输出)

绝地灬酷狼 2022-09-20 12:57 133阅读 0赞

给一个 N\*M 的四方向连通的图, 要从左上角走到右下角，. : 代表可以走，X : 表示是墙，不可以走，n : 代表这里有一个怪兽，打败怪兽用时 n，每走一步耗时 1 .如果能到达，则输出最小时间和每一步的走法。保证起点没有怪兽，终点不是墙，可能有怪兽。

#include<cstring>
    #include<cstdio>
    #include<queue>
    using namespace std;
    
    const int N=105;
    
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    char g[N][N];
    bool vis[N][N];
    int n,m;
    
    struct Node
    {
        int x,y,t;
        int id,pre;
        void Get (int _x,int _y,int _t,int _id,int _pre)
        {
            x=_x;y=_y;t=_t;id=_id;pre=_pre;
        }
        bool operator < (const Node a) const
        {
            return t>a.t;
        }
    }que[N*N];
    
    bool OK (int x,int y)
    {
        return x>=0 && x<n && y>=0 && y<m && g[x][y]!='X' && vis[x][y]==false;
    }
    
    int BFS ()
    {
        int x,y;
        priority_queue<Node> q;
        Node now;
        int cur=0;
        que[cur].Get(0,0,0,0,-1);
        q.push(que[cur++]);
        while (q.empty()==false)
        {
            now=q.top();
            q.pop();
            for (int i=0;i<4;i++)
            {
                x=now.x+dx[i];
                y=now.y+dy[i];
                if (OK(x,y))
                {
                    que[cur].Get(x,y,0,cur,now.id);
                    que[cur].t=now.t+(g[x][y]=='.'?1:g[x][y]-'0'+1);
                    if (x==n-1 && y==m-1)  //到达
                        return cur;
                    q.push(que[cur++]);
                    vis[x][y]=true;
                }
            }
        }
        return -1;
    }
    
    void Output (int id)
    {
        int pre=que[id].pre;
        int x=que[id].x;
        int y=que[id].y;
        int px=que[pre].x;
        int py=que[pre].y;
        if (que[id].pre!=0)
            Output(pre);
    
        printf("%ds:(%d,%d)->(%d,%d)\n",que[pre].t+1,px,py,x,y);
        if (g[x][y]!='.')
        {
            int t=g[x][y]-'0';
            for (int i=1;i<=t;i++)
                printf("%ds:FIGHT AT (%d,%d)\n",que[pre].t+i+1,x,y);
        }
    }
    
    int main ()
    {
        while (~scanf("%d%d",&n,&m))
        {
            for (int i=0;i<n;i++)
                scanf("%s",g[i]);
            memset(vis,false,sizeof(vis));
            int id=BFS();
            if (id!=-1)
            {
                printf("It takes %d seconds to reach the target position, let me show you the way.\n",que[id].t);
                Output(id);
                printf("FINISH\n");
            }
            else
                printf("God please help our poor hero.\nFINISH\n");
        }
        return 0;
    }