o-15题解

先吐槽一下这个题：真的没啥意思，相比n就只多了个路径输出
对于路径的储存我是在结构体中加了一个vector来存储每一步是怎么走的然后再对应输出，因为当vector中存储的数字是‘0’的时候，相当于x+1，为‘1’的时候相当于x-1，U以此类推所以对于我来说这就是一个大型的模拟题了。
就vector存路径解释代码如下

struct node
{
    int x,y;
    int time;
    vector <int>a;
};
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};
在bfs中我们是以for循环来进行左右移动
既for(int i=0;i<4;i++)
{
int nx=x+xx[i];
int ny=y+yy[i];
}
这样来进行移动，所以我们可以存下它的i来表示这一步是怎么走的。当然我们需要把它存在结构体中，其中需要用到插入，所以我选择了vector。

当然这里bfs所用的的队列当然不能是普通队列，得是time小优先的优先队列这样bfs跑出来的结果才是真的最优解。
为了水字数我就再把优先队列的结构体自定义写一下

struct cmp1
{
    bool operator () (const node & a,const node & b) const
    {
       return b.time<a.time;
    }
};
priority_queue<node,vector<node>,cmp1>que;

关于优先队列详情请看我N的题解；
然后就是关于路径的打印了
我当然单独的一个函数，因为这样思路清晰一些，方便后面改错，虽然写的时候真的很折磨；
更多解释在注释里。

void print(node t)
{
    int x1=0,y1=0,nx,ny;
//(x,y)为当前所在点，(nx,ny)为这一步走之后所在的点；
    int u=1;//u来记录这是第几秒方便相应的输出第n秒；
    cout<<"It takes "<<t.time<<" seconds to reach the target position, let me show you the way."<<"\n";
    while(t.a.size())
    {
        if(t.a.front()==0){//这就是在模拟当时那一步是怎么走的
            nx=x1+1;
            ny=y1;
        }else
        if(t.a.front()==1){//这就是在模拟当时那一步是怎么走的
            nx=x1-1;
            ny=y1;
        }else
        if(t.a.front()==2){//这就是在模拟当时那一步是怎么走的
            ny=y1+1;
            nx=x1;
        }else
        if(t.a.front()==3){//这就是在模拟当时那一步是怎么走的
            ny=y1-1;
            nx=x1;
        }
//如果遇到了怪物那么就需要一个循环来输出，
        if(map[nx][ny]>='0'&&map[nx][ny]<='9'){
            cout<<u<<"s:"<<"("<<x1<<","<<y1<<")"<<"->";
        cout<<"("<<nx<<","<<ny<<")"<<"\n";
        u++;
        for(int i=0;i<map[nx][ny]-'0';i++){
        cout<<u<<"s:"<<"FIGHT AT "<<"("<<nx<<","<<ny<<")"<<"\n";
        if(i<map[nx][ny]-'0'-1)u++;    
        }
        }else{
            cout<<u<<"s:"<<"("<<x1<<","<<y1<<")"<<"->";
        cout<<"("<<nx<<","<<ny<<")"<<"\n";
        }
        t.a.erase(t.a.begin());
        x1=nx;//q切记对当前所在点的更新，当走了这一步后，当前点就是走了之后的点了
        y1=ny;
        u++;
    }
}

最后一定记得更新vis数组！！
贴上AC代码

#include<iostream>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;
char map[1000][1000];
bool vis[1000][1000];
int m,n;
struct node
{
    int x,y;
    int time;
    vector <int>a;
};
struct cmp1
{
    bool operator () (const node & a,const node & b) const
    {
       return b.time<a.time;
    }
};
priority_queue<node,vector<node>,cmp1>que;

int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};
int flag=0;
void print(node t);
void bfs(int x,int y)
{
    node e;
    e.x=x;
    e.y=y;
    e.time=0;
    que.push(e);
    vis[0][0]=true;
    node ne;
    while(!que.empty())
    {
        ne=que.top();
    //    cout<<ne.time<<" "<<"\n";
        que.pop();
        if(ne.x==n-1&&ne.y==m-1){
            print(ne);
            flag=1;
            return;
        }
        node e2;
        e2=ne;
        for(int i =0;i<4;i++){
            e2.x=ne.x+xx[i];
            e2.y=ne.y+yy[i];
            e2.time=ne.time;
            e2.a=ne.a;
            if(map[e2.x][e2.y]=='X'||e2.x<0||e2.y<0||e2.x>=n||e2.y>=m||vis[e2.x][e2.y])continue;
            if(map[e2.x][e2.y]>='0'&&map[e2.x][e2.y]<='9')
            {
                e2.time+=map[e2.x][e2.y]-'0'+1;
            }
            else{
                e2.time++;
            }

            e2.a.push_back(i);
            vis[e2.x][e2.y]=true;
            que.push(e2);
        }
    }
} 

void print(node t)
{
    int x1=0,y1=0,nx,ny;
    int u=1;
    cout<<"It takes "<<t.time<<" seconds to reach the target position, let me show you the way."<<"\n";
    while(t.a.size())
    {
        if(t.a.front()==0){
            nx=x1+1;
            ny=y1;
        }else
        if(t.a.front()==1){
            nx=x1-1;
            ny=y1;
        }else
        if(t.a.front()==2){
            ny=y1+1;
            nx=x1;
        }else
        if(t.a.front()==3){
            ny=y1-1;
            nx=x1;
        }
        if(map[nx][ny]>='0'&&map[nx][ny]<='9'){
            cout<<u<<"s:"<<"("<<x1<<","<<y1<<")"<<"->";
        cout<<"("<<nx<<","<<ny<<")"<<"\n";
        u++;
        for(int i=0;i<map[nx][ny]-'0';i++){
        cout<<u<<"s:"<<"FIGHT AT "<<"("<<nx<<","<<ny<<")"<<"\n";
        if(i<map[nx][ny]-'0'-1)u++;    
        }
        }else{
            cout<<u<<"s:"<<"("<<x1<<","<<y1<<")"<<"->";
        cout<<"("<<nx<<","<<ny<<")"<<"\n";
        }
        t.a.erase(t.a.begin());
        x1=nx;
        y1=ny;
        u++;
    }
}
int main(){

    while(cin>>n>>m){
        getchar();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                scanf(" %c",&map[i][j]);
            }
        }
    bfs(0,0);    
    if(flag==0){
        cout<<"God please help our poor hero."<<"\n";
    }

    cout<<"FINISH"<<"\n";
    memset(vis,false,sizeof(vis));
    flag=0;
     while(!que.empty()) {que.pop();} 
    }
    return 0;
}