C - 最後の森 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

長い冒険もようやく終盤を迎え、あとは魔王の城に突入するのみとなった。

魔王の城は「最後の森」と呼ばれる場所にある。最後の森は縦 R 行、横 C 列のマス目で構成されており、それぞれのマスは以下のいずれかである。

  • 平地……平地のマスは自由に通行できる。
  • 木……木のあるマスは通行できない。
  • 強敵のいるマス……凶暴な強敵のいるマスである。後述の条件を満たさなければ通行できない。
  • プレイヤーの村……プレイヤーの初期位置である。このマスは自由に通行できる。
  • ほこら……伝説の剣 Link-Cut Sword があるほこらである。このマスは自由に通行できる。
  • 魔王の城……魔王の城があるマスである。このマスは自由に通行できる。

村のあるマス、ほこらのあるマス、魔王の城があるマスはちょうど 1 つずつである。

以下、i 行 j 列 (1 ≦ i ≦ R,1 ≦ j ≦ C)にあるマスのことをマス (i,j) と呼ぶことにする。2 つの異なるマス (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