HDU 1026 Ignatius and the Princess I

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1026
 
一つのn*mの迷宮には、各格子の中に一つの文字があります.意味は以下の通りです.
        ‘X':行ってはいけません
         ‘.':行ってもいいです
         ’n':次の枠内に行くにはn秒かかります.
問(0、0)から(n−1、m−1)までは最低何秒かかりますか?
分析:優先キュー＋BFS、再帰的にパスを印刷する.
 
ソースコード:

#include<cstdio>
#include<queue>
using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=105;
char map[maxn][maxn];
int stepsum[maxn][maxn];
struct Node1{
	int x,y;
}pre[maxn][maxn];
struct Node2{
	int x,y,sum;
	bool operator <(const Node2 &a)const{
		return sum>a.sum;
	}
}temp,cur;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,m;

void Init(){
	int i,j;
	for(i=0;i<n;i++)
		scanf("%s",map[i]);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			stepsum[i][j]=INF;
}

bool OK(int x,int y){
	if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]!='X') return true;
	return false;
}

bool bfs(){
	priority_queue<Node2>Q;
	temp.x=temp.y=temp.sum=0;
	Q.push(temp);
	stepsum[0][0]=0;
	while(!Q.empty()){
		cur=Q.top();
		Q.pop();
		if(cur.x==n-1&&cur.y==m-1) return true;
		for(int i=0;i<4;i++){
			int tx=cur.x+dir[i][0];
			int ty=cur.y+dir[i][1];
			if(OK(tx,ty)){
				temp.x=tx;
				temp.y=ty;
				temp.sum=cur.sum+1;
				if(map[tx][ty]!='.') temp.sum+=map[tx][ty]-'0';
				if(stepsum[tx][ty]>temp.sum){
					stepsum[tx][ty]=temp.sum;
					pre[tx][ty].x=cur.x;
					pre[tx][ty].y=cur.y;
					Q.push(temp);
				}
			}
		}
	}
	return false;
}

void PrintPath(int x,int y){
	if(x==0&&y==0) return ;
	PrintPath(pre[x][y].x,pre[x][y].y);
	printf("%ds:(%d,%d)->(%d,%d)
",stepsum[pre[x][y].x][pre[x][y].y]+1,pre[x][y].x,pre[x][y].y,x,y);
	if(map[x][y]!='.'){
		for(int i=1;i<=map[x][y]-'0';i++)
			printf("%ds:FIGHT AT (%d,%d)
",stepsum[pre[x][y].x][pre[x][y].y]+i+1,x,y);
	}
}

int main()
{
	while(scanf("%d %d",&n,&m)==2){
		Init();
		if(bfs()){
			printf("It takes %d seconds to reach the target position, let me show you the way.
",stepsum[n-1][m-1]);
			PrintPath(n-1,m-1);
		}
		else printf("God please help our poor hero.
");
		printf("FINISH
");
	}
	return 0;
}