1.Ignatius can only move in four directions(up, down, left, right), one step per second. A step is defined as follow: if current position is (x,y), after a step, Ignatius can only stand on (x-1,y), (x+1,y), (x,y-1) or (x,y+1).
2.The array is marked with some characters and numbers. We define them like this:
. : The place where Ignatius can walk on.
X : The place is a trap, Ignatius should not walk on it.
n : Here is a monster with n HP(1<=n<=9), if Ignatius walk on it, it takes him n seconds to kill the monster.

Your task is to give out the path which costs minimum seconds for Ignatius to reach target position. You may assume that the start position and the target position will never be a trap, and there will never be a monster at the start position.

Input
The input contains several test cases. Each test case starts with a line contains two numbers N and M(2<=N<=100,2<=M<=100) which indicate the size of the labyrinth. Then a N*M two-dimensional array follows, which describe the whole labyrinth. The input is terminated by the end of file. More details in the Sample Input.

Output
For each test case, you should output "God please help our poor hero." if Ignatius can't reach the target position, or you should output "It takes n seconds to reach the target position, let me show you the way."(n is the minimum seconds), and tell our hero the whole path. Output a line contains "FINISH" after each test case. If there are more than one path, any one is OK in this problem. More details in the Sample Output.

Sample Input
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.

Sample Output
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

Author
Ignatius.L

题意：

给你一个 N*M 的图, 要你从第一个点走到最后一个点【从左上角走到右下角】
只可以按照上下左右四个方向走

. : 代表可以走

X : 表示是墙，不可以走

n : 代表这里有一个怪兽，打败怪兽用时 n

每走一步耗时 1 .

如果能到达，则输出最小时间和每一步的走法
不能到达输出。。。
具体输出看样例。

注意：保证起点没有怪兽，终点不是墙。【也就是说终点可能有怪兽】

算法：优先队列+BFS 【本质Dijkstra】

思路：

很裸的最短路了，但是不熟悉优先队列，用自己的笨方法错了很久。

正解思路：

由于是用的优先队列+BFS 为了方便输出路径,所以从终点开始搜索。
从起点开始也可以，只是不方便，要么递归输出路径点击打开链接
要么定义一个数组来维护，使得本来就很复杂了的简单题目越发变得复杂起来。

定义一个优先队列，包含了位置和当前位置到达终点的最短时间。
优先队列保证时间短的先出队。。。

//定义优先队列：对于入队了的点,先出队的是时间少的,那么第一个到达终点的就是结果
struct Node{
    int x,y; //当前到达的点
    int time; //耗费的时间

    bool operator < (const Node &b) const{
        return b.time < time;
    }
};

关于优先队列的重载一直不是很清楚。。。