AT_wupc2012_3 自宅からの脱出

[problemUrl]: https://atcoder.jp/contests/wupc2012/tasks/wupc2012_3 僕が入力したパスワードは正しかったようだ．とりあえず，参加資格は剥奪されずに済んだ．しかし，圧縮ファイルを解凍するにはまだしばらく時間が掛かるようだった． ふと，僕はここ数日家から一歩も外に出ていないことに気づいた．そして，当日，時間通りに家から出られるだろうか……と不安になってきた．というのも，僕の家は迷路のように複雑な入り組んだ構造をしており，適切な移動経路を選択しないと時間がかかりすぎてしまうからだ．コンテスト当日までに，家から出るために必要な時間を見積もっておきたい． さらに，僕の家にはコンテストで使うノートブック型計算機がある．家を出るのは，もちろんそれを回収した後でなければならない．つまり，僕の部屋を出て，計算機を回収し，家を出るまでの最短時間を求めておく必要がある． 家の見取り図のデータが文字列で与えられる．見取り図のデータは二次元の座標平面上に表すことができる．見取り図は北を上にして書かれており， 北西端の座標を $ (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 $ を出力せよ．

N/A

N/A