原题大意

迷宫题,要求求出最短时间,同时打印每一个步骤.

算法分析

看到这题,我的第一反应就是bfs,但是,还要打印每一步,我没什么办法,百度后普遍算法是,用优先队列bfs得出最小路径后,递归打印.
首先优先队列的优先级别要能改

struct Point{
int x,y;
int time;
friend bool operator<(Point a,Point b)
{
    return a.time>b.time;
}
};

注意:stl里优先队列只能对<重载.
记录路径的方法是:用数组Point,当前数组的值为上一步的坐标,打印时递归.

程序代码

#include <iostream>
#include <queue>
using namespace std;
int n,m;//对应N,M 
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
char lab[110][110];//迷宫
struct Point{
    int x,y;
    int time;
    friend bool operator<(Point a,Point b)
    {
        return a.time>b.time;
    }
};
Point path[110][110];//保存路径 
Point e;//终点
void bfs()
{
    priority_queue<Point> q;
    Point sta;
    sta.x=sta.y=sta.time=0;
    q.push(sta);
    while(!q.empty())
    {
        Point s;
        s=q.top();
        q.pop();
        if(s.x==n-1&&s.y==m-1) 
        {
            e.time=s.time;
            return;
        }
        for(int i=0;i<4;i++)
        {
            Point t;
            t.x=s.x+dx[i];
            t.y=s.y+dy[i];
            if(t.x<0||t.y<0||t.x>=n||t.y>=m||lab[t.x][t.y]=='X') continue;
            t.time=s.time+1;
            path[t.x][t.y].x=s.x;//记录前驱
            path[t.x][t.y].y=s.y;
            path[t.x][t.y].time=0;//若是'.'时间为0
            if(lab[t.x][t.y]!='.')
                {
                    t.time+=lab[t.x][t.y]-'0';
                    path[t.x][t.y].time=lab[t.x][t.y]-'0';
                }
            lab[t.x][t.y]='X';//走过后就标为"X",避免往回走
            q.push(t);
        }
    }    
}
void print(int time,int i,int j)
{
    if(time==0) return;
    time-=path[i][j].time;
    print(time-1,path[i][j].x,path[i][j].y);
    printf("%ds:(%d,%d)->(%d,%d)\n",time++,path[i][j].x,path[i][j].y,i,j);
    while(path[i][j].time--)
    {
            printf("%ds:FIGHT AT (%d,%d)\n",time++,i,j);
    }


}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)//不加!=EOF会超时
    {
        for(int i=0;i<n;i++)
                scanf("%s",lab[i]);
        e.time=-1;
        bfs();
        if(e.time==-1) printf("God please help our poor hero.\n");
        else 
        {
            printf("It takes %d seconds to reach the target position, let me show you the way.\n",e.time);    
            print(e.time,n-1,m-1);
        } 
     printf("FINISH\n");  
    }
    return 0;
}