Ignatius and the Princess I

/*题意：很好理解，就是迷宫的搜索问题嘛，找出一条最短的从(0,0)到(n-1,m-1)，遇到怪物还要花费相应的时间进行消灭才能通过。然后打印    路径，输出最短的时间。初步思路：先进行bfs加一个优先队列进行剪枝，找到最短时间之后，再打印路径。#错误：用bfs加优先队列的时候遇到问题，并不能得到最优解,擦掉重写一发#改进：果然是写残了，重写了一发就可以了，剩下的就是打印路径的问题了，用一个path数组记录路径，然后递归进行打印路径#重点：又交了一发wa了，看了一下discuss，漏了一种情况，起点也是可能有守卫的#错误：不知道为啥，加上这种情况还是wa#改进：重新找到错误了，在处理最后一步的时候，路径记录的不准确        这组数据很关键        3 3        ...        .X.        ..8        如果有两条路的话就不行了，所以递归的时候要从后往前递归*/#include<bits/stdc++.h>using namespace std;int n,m;char mapn[110][110];int vis[110][110];int path[110][110];//用于记录路径int Time,cur;int dir[4][2]={1,0,-1,0,0,1,0,-1};struct node{    int x,y;//位置    int times;//用到的时间    node(){}    node(int a,int b,int c){        x=a;        y=b;        times=c;    }    bool operator <(const node& other)const{        return times>other.times;    }};bool ok(int x,int y){    if(x<0||x>=n||y<0||y>=m||mapn[x][y]==‘X‘||vis[x][y])        return true;    return false;}int bfs(){    memset(vis,0,sizeof vis);    priority_queue<node>q;    if(mapn[0][0]==‘.‘)        q.push(node(0,0,0));    else if(mapn[0][0]>=‘0‘&&mapn[0][0]<=‘9‘){        q.push(node(0,0,mapn[0][0]-‘0‘));        Time+=mapn[0][0]-‘0‘;    }    vis[0][0]=1;    while(!q.empty()){        node fa=q.top();        q.pop();        //cout<<fa.x<<" "<<fa.y<<endl;        if(fa.x==n-1&&fa.y==m-1)            return fa.times;        for(int i=0;i<4;i++){            int fx=fa.x+dir[i][0];            int fy=fa.y+dir[i][1];            if(ok(fx,fy)) continue;            //printf("(%d,%d)->(%d,%d)\n",fa.x,fa.y,fx,fy);            path[fx][fy]=i;//走的是第几步            //cout<<fa.x<<" "<<fa.y<<" "<<path[fa.x][fa.y]<<endl;            vis[fx][fy]=1;            if(mapn[fx][fy]==‘.‘){                q.push(node(fx,fy,fa.times+1));            }else{                q.push(node(fx,fy,fa.times+(mapn[fx][fy]-‘0‘)+1));                // cout<<fx<<" "<<fy<<" 这地方有守卫"<<endl;            }        }    }    return -1;}void print(int x,int y){    if(path[x][y]==-1){        return;    }    int next_x=x-dir[path[x][y]][0];    int next_y=y-dir[path[x][y]][1];    print(next_x,next_y);    printf("%ds:(%d,%d)->(%d,%d)\n",Time++,next_x,next_y,x,y);    if(mapn[x][y]>=‘0‘&&mapn[x][y]<=‘9‘){        int res=mapn[x][y]-‘0‘;        while(res--){            printf("%ds:FIGHT AT (%d,%d)\n",Time++,x,y);        }    }}void init(){    Time=1;    memset(path,-1,sizeof path);}int main(){    // freopen("in.txt","r",stdin);    while(scanf("%d%d",&n,&m)!=EOF){        // cout<<n<<" "<<m<<endl;         init();        for(int i=0;i<n;i++){            scanf("%s",&mapn[i]);            // cout<<mapn[i]<<endl;        }//输入地图        cur=bfs();        if(cur==-1) 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",cur);            if(Time!=1){                for(int i=1;i<Time;i++){                    printf("%ds:FIGHT AT (0,0)\n",i);                }            }            print(n-1,m-1);        }        puts("FINISH");    }    return 0;}