HDU 1026 Ignatius and the Princess I

    题目大意：从(0, 0)，走到(x-1, y-1)所需要的最短时间

   （1）'.'为路需要1个单位的时间， 'X'不能走；

   （2）为数字表示打怪需要的时间，而走到这一步需要1个单位的时间，所以 使用的时间 = 打怪时间 + 1

    思路：

   

//数据1
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX.

     广度优先遍历

           

 

     由此可以算出最少的时间

     又因为每一个点的时间都是由前一个点的时间得到的，所以这一个点有且只有前一个点，记录每一个点的前一个点

          

 

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
using namespace std;
#define MAX 500
char m[MAX][MAX];
int v[MAX][MAX];
int x, y, flag;
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
struct Node
{
	int x, y, num;
	friend bool operator <(Node a, Node b)
	{
		return a.num > b.num;
	}
};
Node pre[MAX][MAX];
int main()
{
    int i, j;
	Node tmp, s;
	while (scanf("%d%d", &x, &y)!=EOF)
	{
		for (i=0; i<x; i++)
			for (j=0; j<y; j++)
				cin>>m[i][j];
		flag = 0;
		memset(v, 0, sizeof(v));
       priority_queue<Node>q;
		v[0][0] = 1;
		pre[0][0].x = pre[0][0].y = -1;
		tmp.x = tmp.y = 0;
		tmp.num=0;
		q.push(tmp);
		while (!q.empty())
		{
			tmp = q.top();
			q.pop();
			if (tmp.x==x-1 && tmp.y==y-1)
			{
				printf("It takes %d seconds to reach the target position, let me show you the way.\n", tmp.num);
				flag = 1;
				break;
			}
			for (i=0; i<4; i++)
			{
               s.x = tmp.x + dx[i];
			   s.y = tmp.y + dy[i];
			   if (m[s.x][s.y]!='X' && s.x>=0 && s.y>=0 && s.x<x && s.y<y && !v[s.x][s.y])
			   {
				   if (m[s.x][s.y]=='.')
					   s.num = tmp.num + 1;
				   else
					   s.num = tmp.num + m[s.x][s.y] - '0'+1;
				   pre[s.x][s.y].y = tmp.y;
				   pre[s.x][s.y].x = tmp.x;
				   v[s.x][s.y] = 1;
			       q.push(s);
			   }
			}
		}
		if (flag==1)
		{
			for (i=0; i<x; i++)
			{
				for (j=0; j<y; j++)
					cout<<pre[i][j].x<<" "<<pre[i][j].y<<"     ";
				cout<<endl;
			}
		   stack<Node>sta;
		   s.x = x-1;
		   s.y = y-1;
		   sta.push(s);
		   while (s.x!=-1||s.y!=-1)
		   {
			   sta.push(pre[s.x][s.y]);
			   int tx = s.x, ty = s.y;
			   s.x = pre[tx][ty].x;
			   s.y = pre[tx][ty].y;
		   }
		   sta.pop(); 
		   s = sta.top();
		   sta.pop();
		   int time = 1;
		   while (!sta.empty())
		   {
			   tmp = sta.top();
			   sta.pop();
			   if (m[tmp.x][tmp.y]=='.')
			   {
				   printf("%ds:(%d,%d)->(%d,%d)\n", time,s.x, s.y, tmp.x, tmp.y );
				   time++;
			   }
			   else
			   {
				   printf("%ds:(%d,%d)->(%d,%d)\n", time,s.x, s.y, tmp.x, tmp.y );
				   time++;
				   for (i=0; i<m[tmp.x][tmp.y]-'0'; i++)
				   {
					   printf("%ds:FIGHT AT (%d,%d)\n", time, tmp.x, tmp.y);
					   time++;
				   }
			   }
			   s.x = tmp.x;
			   s.y = tmp.y;
		   }
		}
		else
			printf("God please help our poor hero.\n");
		printf("FINISH\n");
	}
	return 0;
}