ACM Ignatius and the Princess I

公主被BEelzebub feng5166绑架，我们的英雄Ignatius必须拯救我们美丽的公主。现在他进入feng5166的城堡。城堡是一个大迷宫。为简单起见，( To make the problem simply, )我们假设迷宫是一个N * M二维数组，左上角是（0,0），右下角是（N-1，M-1）。 Ignatius进入（0,0），feng5166的房间的门是（N-1，M-1），这是我们的目标。城堡里有一些怪物，如果Ignatius遇见他们，他必须杀死他们。这里有一些规则：

1.Ignatius只能在四个方向（上，下，左，右）移动，每秒一步。步骤定义如下：如果当前位置是（x，y），步骤之后，Ignatius只能站立（x-1，y），（x + 1，y），（x，y-1）或（X，Y + 1）。
2.数组标有一些字符和数字。我们定义如下：
. : Ignatius可以走的地方
X :这个地方是一个陷阱，Ignatius不应该走在它上面。
n : 这是一个n HP（1 <= n <= 9）的怪物，如果Ignatius走在上面，则需要他n秒才能杀死怪物。
您的任务是发出Ignatius到达目标位置的最小秒数的路径。你可以假设起始位置和目标位置永远不会成为陷阱，在起始位置永远不会有怪物。

Input

该输入包含几个测试用例。每个测试用例以包含两个数字N和M（2 <= N <= 100,2 <= M <= 100）的行开始，表示迷宫的大小。然后是一个N * M二维阵列，它描述了整个迷宫。输入结束文件结束。样品输入中的更多细节。
Output

对于每个测试用例，如果Ignatius不能达到目标位置，你应该输出 "God please help our poor hero." 或者你应该输出"It takes n seconds to reach the target position, let me show you the way."(n is the minimum seconds), 告诉我们的英雄的整个路径。在每个测试用例之后输出一行包含“FINISH”。如果有不止一个路径，任何一个都可以在这个问题。样品输出中的更多细节。

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

巴特西

ACM Ignatius and the Princess I

最新文章

热门文章