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 自动生成**
输入格式
无
输出格式
无