hdu 1026 Ignatius and the Princess I（广搜+优先队列+路径保存）

看题目请点这里

题意：

n、m分别为地图的行列数，从（0,0）点走到（n-1,m-1）点。

‘.’可走的点，花费时间1；‘X’不可走的点；数字可走，花费时间1+数字。

格式见样例。

代码：

#include<queue>#include<stack>#include<cstring>#include<iostream>using namespace std ; const int N=101;struct node{    int x, y, x_next, y_next,t ;//x、y：当前所在的点；x_next、y_next：下一步要去的点    friend bool operator<(node c, node d)//优先队列：t小的优先级高     {        return c.t>d.t ;     }    }first,next,final,path[N][N]; int n,m,i; int dir[4][2]={0,1, 0,-1, 1,0, -1,0};bool flag[N][N];//标记有无走过char map[N][N] ;stack<node>S;int bfs(){    priority_queue<node>Q;first.x=first.y=first.t=0;    Q.push(first);//进队列    while(!Q.empty())    {        first=Q.top();         Q.pop();//出队列if(first.x==n-1 && first.y==m-1){final.x=first.x;//final保存终点位置的nodefinal.y=first.y; final.x_next=final.y_next=0; return first.t;}        for(i=0;i<4;i++)        {            next.x=first.x+dir[i][0] ;             next.y=first.y+dir[i][1] ;              if(next.x>=0 && next.x<n && next.y>=0 && next.y<m && map[next.x][next.y]!='X' && flag[next.x][next.y]==0){next.t=first.t+1;if(map[next.x][next.y]!='.'){next.t+=(map[next.x][next.y]-'0');//加上在此战斗花费的时间}flag[next.x][next.y]=1;Q.push(next);first.x_next=next.x;//保存在(first.x，first.y)要去的下一个点坐标first.y_next=next.y; path[next.x][next.y]=first;//path保存在每个点的状态}        }    }return 0;}    int main(){   int ans;    while(scanf("%d %d", &n,&m)!=EOF)    {        for(i=0;i<n;i++)        {scanf("%s",map[i]);         }memset(flag,0,sizeof(flag));ans=bfs();if(ans==0){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",ans);S.push(final);//终点先逆序入栈 node temp=path[final.x][final.y]; while(temp.x || temp.y)//条件成立时，即到了(0,0)点 {S.push(temp); temp=path[temp.x][temp.y]; } S.push(temp);//(0,0)点入栈int num=1;//记录时间while(!S.empty())//出栈，输出路径{ temp=S.top(); S.pop(); if(map[temp.x][temp.y]=='.' && !(temp.x_next==0 && temp.y_next==0))//!(...)保证在终点时不会往下走{printf("%ds:(%d,%d)->(%d,%d)\n",num++,temp.x,temp.y,temp.x_next,temp.y_next); }else if(map[temp.x][temp.y]>='1' && map[temp.x][temp.y]<='9') { for(i=0;i<map[temp.x][temp.y]-'0';i++) {printf("%ds:FIGHT AT (%d,%d)\n",num++,temp.x,temp.y); }if(!(temp.x_next==0 && temp.y_next==0)) {printf("%ds:(%d,%d)->(%d,%d)\n",num++,temp.x,temp.y,temp.x_next,temp.y_next); }} } } puts("FINISH");}return 0 ; }