AT_arc019_3.[ARC019C] 最後の森

魔王的城堡坐落在名为「最后的森林」的地方。这个森林由 $R$ 行 $C$ 列的网格构成，每个格子可能是以下几种类型：

• 平地：可以自由通行。
• 树木：此格子不能通行。
• 强敌：有凶恶的强敌阻挡，需要特定条件才能通过。
• 村庄：玩家的起始位置，可以自由通行。
• 神殿：存放传说之剑 Link-Cut Sword，可以自由通行。
• 魔王的城堡：魔王所在位置，可以自由通行。

村庄、神殿和魔王的城堡各自只有一个。

我们称第 $i$ 行第 $j$ 列的格子为 $(i, j)$。如果两个格子相邻，意味着它们共享一个边，即以下两种情况之一成立：

• 在同一行，两列相邻。
• 在同一列，两行相邻。

玩家初始位置在村庄。玩家可以执行以下两种操作：

• 移动到相邻的格子，前提是该格子允许通行。
• 与相邻格子中的强敌战斗。战胜敌人后，该格子可以通行。

在与魔王对峙之前，玩家需要提升自己的装备（道具）。取得神殿中的传说之剑是战胜魔王的必要条件。因此，玩家需要先获取传说之剑，然后前往魔王的城堡。即便不拿剑，也可以路过魔王的城堡，但最多只能与 $K$ 次强敌交锋。

由于森林中弥漫着魔王的剧毒雾气，玩家需要尽可能减少移动时间。请编写程序，计算出满足条件的最短路径的移动次数。如果没有符合条件的路径，输出 -1。

输入格式

第一行为三个整数 $R, C, K$，分别表示森林的行数、列数和允许战斗的最大次数。

接下来 $R$ 行，每行包含一个长度为 $C$ 的字符串，描述森林的格子种类。其中：

• . 表示平地
• T 表示树木
• E 表示强敌
• S 表示村庄
• C 表示神殿
• G 表示魔王的城堡

输出格式

输出满足条件的最短路径的移动次数。如果没有符合条件的路径，则输出 -1。

示例

输入例 1

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

输出例 1

19

输入例 2

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

输出例 2

21

输入例 3

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

输出例 3

-1

输入例 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

本翻译由 AI 自动生成