← 返回题目列表

AtCoder · arc019_3

C. 最后的森林

中文机器翻译题面 查看原题

漫长的冒险终于结束了,剩下的就是冲进魔王的城堡了。

魔王的城堡位于名为“最后的森林”的地方。最后的森林是垂直的 R 行、横 C 它由一列方块组成,每个方块都是以下之一。

  • 平地...你可以自由地穿过平地广场。
  • 树...你不能穿过有树的方格。
  • 一个有强敌的方阵...一个有凶猛强敌的方阵。除非满足下述条件,否则无法通过。
  • 玩家的村庄...这是玩家的初始位置。这个广场可以自由通过。
  • 霍科拉...传奇之剑 连斩剑 这是一个神社,里面有一个 。这个广场可以自由通过。
  • 魔王城……这是魔王城所在的广场。这个广场可以自由通过。

有村庄的广场,有神社的广场,有魔王城堡的广场就在 1 一一。

以下、i 行 j 列 (1 ≦ i ≦ R,1 ≦ j ≦ C)我们称之为 (i,j) 。2 3 个不同的方块 (i,j),(k,l) (i 和 k 是1 ≦ i,k ≦ R 的,j 和 l 是 1 ≦ j,l ≦ C 很满意, 如果(i,j) ≠ (k,l) ) 共享一条边,即满足以下条件,则定义为相邻: 与

  • i = k 和 j 和 l 的差的绝对值为 1 。
  • j = l 和 i 和 k 的差的绝对值为 1 。

玩家最初位于村庄广场。玩家可以执行以下操作。

  • 移动到与玩家所在方格相邻的方格。此时,目的地方格必须是可以自由通过的方格。
  • 在与玩家方格相邻的方格中与强敌作战。与你战斗的强敌将会被清除,从此你就可以自由地穿越那片空间了。

与魔王的战斗需要高难度的编程技能。为了面对魔王,必须强化自己的装备(图书馆)。尤其是,如果不拿到神社里的传说之剑,就无法打倒魔王。所以,我想先去神社拿到传说之剑,然后再去魔王城。在没有获得传说之剑的情况下,可以通过魔王城所在的广场。

另外,与生活在最终森林中的强敌的战斗是艰难的,所以你可以在获得传奇之剑之前和之后进行选择。 K 我想让战斗不超过一次。

最后的森林里充满了魔王散发出的剧毒雾气,所以我们必须尽可能缩短行进的时间。直到最后,这都是一场艰难的比赛。因此,有必要使用一个程序来找出满足上述条件的可能行驶路线中使行驶次数最少的行驶次数。


入力

输入是按以下格式从标准输入给出的。
R C K
s_{(1,1)} s_{(1,2)}  … s_{(1,C)}
s_{(2,1)} s_{(2,2)}  … s_{(2,C)}
:
s_{(R,1)} s_{(R,2)}  … s_{(R,C)}
  1. 1 行中,3 整数 给出了 R,C,K(R 和 C 是 1 ≦ R,C ≦ 50 的,K 是 0 ≦ K ≦ 100 ) 给出,用空格分隔。
  2. 2 从行 R 次、长度 字符串 C 是 1 逐行给出。每个字母都是 .,T,E,S,C,G , 赋予i 回目 (1 ≦ i ≦ R) 的字符串 关于 j 文字目 (1 ≦ j ≦ C) ,
    • 那个字符 . 然后,质量 (i,j) 是一个扁平的正方形
    • 那个字符 T 然后,质量 (i,j) 是一个有树的正方形
    • 那个字符 E 然后,质量 (i,j) 是一个有强敌的方格
    • 那个字符 S 然后,质量 (i,j) 是村庄所在的广场。
    • 那个字符 C 然后,质量 (i,j) 必须是一个有神殿的正方形。
    • 那个字符 G 然后,质量 (i,j) 是魔王城所在的广场。 代表
    。村庄所在的广场、神社所在的广场、魔王城所在的广场都是一模一样的 1 一一。

出力

编写一个输出最小移动次数的程序。如果没有满足条件的出行路线, -1 。

请在输出末尾添加换行符。


入力例 1

5 7 3
GET..ET
..T....
.TEST..
.E.T.ET
...ETC.

出力例 1

19
  • 玩家优先 我在 (3,4) 。例如,移动如下。
    1. 质量 来自 (3,4) 转至 (3,6) 。
      • 最小值 有必要执行 4 移动动作。
      • 移动完成后,总移动次数为 4 次,总战斗次数为 0 次。 在
    2. 质量 来自 (4,6) 中与强大的敌人作战。
      • 战斗结束时,总步数为 4 次,总战斗次数为 1 次。 在
    3. 质量 来自 (3,6) 有灰尘的方形 (5,6) 。
      • 最小值 有必要执行 2 移动动作。
      • 移动完成后,总移动次数为 6 次,总战斗次数为 1 次。 在
    4. 有神社的广场 从 (5,6) 转至 (3,4) 。
      • 最小值 有必要执行 6 移动动作。
      • 移动完成后,总移动次数为 12 次,总战斗次数为 1 次。 在
    5. 质量 来自 (3,3) 中与强大的敌人作战。
      • 战斗结束时,总步数为 12 次,总战斗次数为 2 次。 在
    6. 质量 来自 (3,4) 转至 (4,3) 。
      • 最小值 有必要执行 2 移动动作。
      • 移动完成后,总移动次数为 14 次,总战斗次数为 2 次。 在
    7. 质量 来自 (4,2) 中与强大的敌人作战。
      • 战斗结束时,总步数为 14 次,总战斗次数为 3 次。 在
    8. 质量 来自 (4,3) 前往魔王城所在的广场。 与 (1,1) 。
      • 最小值 有必要执行 5 移动动作。
      • 移动完成后,总移动次数为 19 次,总战斗次数为 3 次。 在

入力例 2

5 7 2
GET..ET
..T....
.TEST..
.E.T.ET
...ETC.

出力例 2

21
  • 入力例 1 相比,可进行的战斗较少,所以你需要走更长的弯路。 在

入力例 3

5 7 1
GET..ET
..T....
.TEST..
.E.T.ET
...ETC.

出力例 3

-1
  • 入力例 3 中,没有满足条件的路由。

入力例 4

6 35 4
T...TT.....TT...TTT...TTT..TTG.....
..T..T.TTT.T..T..E..T..E...TTT.TTT.
.TTT.T.....E.TTTTT.TTT.TTT.TTT.....
.....T.TT.TT.TTTTT.TTT.TTT.TTTTTTT.
.TTT.T.TT..T..T..S..T..TTT.TTTTTTT.
.CTT.E.TTT.TT...TTT...TT.....E.....

出力例 4

94