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

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保存终点位置的node
			final.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 ; 
}