C - 自宅からの脱出 Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

　僕が入力したパスワードは正しかったようだ．とりあえず，参加資格は剥奪されずに済んだ．しかし，圧縮ファイルを解凍するにはまだしばらく時間が掛かるようだった．

　ふと，僕はここ数日家から一歩も外に出ていないことに気づいた．そして，当日，時間通りに家から出られるだろうか……と不安になってきた．というのも，僕の家は迷路のように複雑な入り組んだ構造をしており，適切な移動経路を選択しないと時間がかかりすぎてしまうからだ．コンテスト当日までに，家から出るために必要な時間を見積もっておきたい．

　さらに，僕の家にはコンテストで使うノートブック型計算機がある．家を出るのは，もちろんそれを回収した後でなければならない．つまり，僕の部屋を出て，計算機を回収し，家を出るまでの最短時間を求めておく必要がある．

問題文

　家の見取り図のデータが文字列で与えられる．見取り図のデータは二次元の座標平面上に表すことができる．見取り図は北を上にして書かれており， 北西端の座標を (1,1) とすると，北東端の座標は (M,1)，南東端の座標は (M,N) となる．
座標 (x,y) の情報は y 行目の x 文字目に書かれており， 
 . : 部屋
 # : 壁
 C : 計算機がある場所
 S : 「僕」の部屋
 G : 家の玄関
をそれぞれ表している．「僕」は 1 単位時間をかけて現在位置 (x,y) から東西南北のいずれかの方向に 1 進むことができる．
すなわち，(x+1,y),(x-1,y),(x,y+1),(x,y-1) のいずれかに進むことができる．ただし，移動先の座標が 
　# : 壁 である場合には移動できない．
　C : 計算機がある場所 である場合はそこへ移動した後，計算機を回収したことになる．このとき，回収にかかる時間は無視できる．
　G : 家の玄関である場合は，もしその時点で計算機を回収していたならゴールとなる．そうでない場合は何も起こらない．
　「僕」が僕の部屋から出てゴールするまで(＝計算機を回収した状態で家の玄関にたどり着くまで)の最短時間を出力するプログラムを作成せよ．ただし，玄関までたどり着くことが不可能であったり，計算機を回収できない時は -1 を出力してほしい．
なお，見取り図は壁で囲われていることが保証される．

図1：入力例 1の解答

入力

入力は以下の形式で標準入力から与えられる． 
N　M
S_{1}
S_{2}
...
S_{N}
  • 1 行目に自宅のサイズを表す N(5 ≦ N ≦ 500) と M(5 ≦ M ≦ 500) が半角スペース区切りで与えられる．
  • 2 行目から N+1 行目には，M 文字の文字列が与えられる．これらは家の見取り図のデータである．
  • 文字列中に出現する文字列は '.', '#', 'C', 'S', 'G' のいずれかであり，意味は上に記した通りである．
  • S_{1}とS_{N}は '#' 以外の文字は含まず，またN行の各文字列の最初と最後の文字は必ず '#' である．
  • 'C', 'S', 'G'の各文字は，それぞれ必ず 1 つだけ出現する．

出力

「僕」の部屋からスタートし，計算機を回収した状態で玄関へたどり着くまでの最短時間を一行に出力せよ．
ただし，そのような移動が不可能である場合は -1 を出力せよ．

入力例 1

5 5
#####
#S..#
#.C.#
#..G#
#####

出力例 1

4

入力例 2

7 7
#######
#S....#
#...#.#
#...#C#
#...###
#G....#
#######

出力例 2

16

入力例 3

7 7
#######
#S....#
#.###.#
#.#C#.#
#.###.#
#....G#
#######

出力例 3

-1
  • 計算機を回収できないので，ゴールできない．よって，-1を出力する．

Source Name

WUPC 2012