其实玩游戏也得学程序

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

由于前两次的打击,ZYJ同学不再喜欢密码学,他喜欢上了游戏。某一天,他要玩魔塔这个游戏,游戏规则是这样的,游戏地图的大小为N*M,一开始,ZYJ处于(0,0)点,ZYJ想去(N-1,M-1)点。但是通往目标的路上有很多妖怪,每个妖怪都会打掉ZYJ不同数量的血量。现在ZYJ希望能够耗费最少的血量到达目的地。

但是他必须遵循以下规则:

1 他只能走上下左右四个方向。

2 每一个格可能为“.”“X”或者数字,“.”表示可以走,但是由于ZYJ身体虚弱,走的时候要扣掉1点血量值,“X”表示墙壁不可以走,数字表示这个怪物(数字大于等于1小于等于9)会打掉ZYJ的血量值。

而现在你的任务就是计算怎么样才能耗费最小的血量到达目的地。(毕竟ZYJ也不容易,连着受了两次打击,千万别再让他耗费过多的血量了,祖国需要这样的栋梁啊。。。。)

Input

 

输入包含多组数据,每一组数据第一行都有两个整数N,M,他们表示N*M的地图,接下来就是N行,长为M的迷宫。 (2<=N<=100,2<=M<=100),当输入的n=0,m=0的时候结束。

Output

 

如果无法到达目的地,就输出"GAME OVER.",如果可以找到,那么就把路径以样例的形式显示出来。输出的s代表的是耗费的血量的单位。不管能不能找到,在最后都输出一个"FINISH".

Sample Input

5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX.
0 0

Sample Output

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

Hint

 

Source

ZYJ