Ignatius and the Princess I

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7141    Accepted Submission(s): 2137
Special Judge

5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX.
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX1
5 6
.XX...
..XX1.
2...X.
...XX.
XXXXX.

It takes 13 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
FINISH
It takes 14 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
14s:FIGHT AT (4,5)
FINISH
God please help our poor hero.
FINISH

解题思路：实质就是一个图的最短路径问题，可以采用bsf搜索，并且结合使用优先级队列。

代码如下：

//杭电1026

#include <iostream>
#include <queue>
#include <stack>
#include <fstream>
using namespace std;
int dir[][2] = {{-1,0},{1,0},{0,-1},{0,1}};
typedef struct node 
{
	int i, j;
	int time;
	friend bool operator<(node n1, node n2)//按照时间大小从小到大排列
	{
		return n1.time > n2.time;
	}
}Node;
typedef struct 
{
	int i;
	int j;
}Point;
char map[100][100];//记录整个地图
bool used[100][100];//标记是否已经搜索过
Point result[100][100];//记录达到某一点的前一个位置，通过回溯找到路径
int n, m;//表示地图的大小

int bfs()//广度搜索，返回到达终点的最小时间数值
{
	priority_queue<Node> Q;//优先级队列
	Node start;
	start.i = 0;
	start.j = 0;
	start.time = 0;
	Point tempP;
	tempP.i = -1;
	tempP.j = -1;
	result[0][0] = tempP;
	used[0][0] = true;
	Q.push(start);
	while(!Q.empty())
	{
		Node tempN = Q.top();
		Q.pop();
		for (int k = 0; k < 4;  ++ k)
		{
			int ni = tempN.i + dir[k][0];
			int nj = tempN.j + dir[k][1];
			if (ni >= 0 && ni < n && nj >= 0 && nj < m && !used[ni][nj] && map[ni][nj] != 'X')
			{
				Node temp;
				temp.i = ni;
				temp.j = nj;
				if (map[ni][nj] == '.')
					temp.time = tempN.time + 1;
				else
					temp.time = tempN.time + map[ni][nj] - '0' + 1;
				used[ni][nj] = true;
				Point tp;
				tp.i = tempN.i;
				tp.j = tempN.j;
				result[ni][nj] = tp;
                
				if (ni == n - 1 && nj == m - 1)
					return temp.time;
				Q.push(temp);
			}
		}
	}
	return -1;
}

int main ()
{
	//ifstream in("in.txt");
	while (cin >> n >> m)
	{
        
		
		for (int i = 0; i < n ; ++ i)
			for (int j = 0; j < m ; ++ j)
			{
				cin>>map[i][j];
				used[i][j] = false;
			}
		//cout<< "输入完毕！"<<endl;
		int t = bfs();
		if (t == -1)
        {
            cout<<"God please help our poor hero."<<endl;
            cout <<"FINISH"<<endl;
        }
        
		if (t != -1)
		{
            cout <<"It takes "<<t<<" seconds to reach the target position, let me show you the way."<<endl;
			stack<Point> path;
			Point pp ;
			pp.i = n - 1;
			pp.j = m - 1;
			path.push(pp);
			while (result[pp.i][pp.j].i != -1 && result[pp.i][pp.j].j != -1)
			{
				path.push(result[pp.i][pp.j]);
				pp = result[pp.i][pp.j];
			}
			int time = 1;
			pp = path.top();
			path.pop();
			while(!path.empty())
			{
				cout << time<<"s:("<<pp.i<<","<<pp.j<<")->("<<path.top().i<<","<<path.top().j<<")"<<endl;
				time ++;
				if (map[path.top().i][path.top().j] != '.')
				{
					int tt = map[path.top().i][path.top().j] - '0';
					for (int mm = 0; mm < tt; ++ mm)
					{
						cout <<time<<"s:FIGHT AT ("<<path.top().i<<","<<path.top().j<<")"<<endl;
						time ++;
					}
				}
				
				pp = path.top();
				path.pop();
			}
            cout <<"FINISH"<<endl;
		}
		
		
	}
	//in.close();
	return 0;
}