0084 - 迷路の問題だよ!

時間制限 1 秒 / メモリ制限 32 MB / 得点 4 / Writer ei1428 / x 31 / 統計 /


TLE
1sec
MLE
32MB
得点
4

問題

あるH高校にMr.fourがいました。
Mr.fourは「ラヲライブ ロリコンオメガフェスティバル」が大好きです。このゲームはある迷路を早くクリアするゲームです。Mr.fourはプライドが高いので、なんとしても4位を取りたいそうです。なので、迷路を最短で進む必要があるようです。しかし、Mr.fourは頭が悪いのです。( 数学4((以下略 )
頭のいいみんながMr.fourを救ってあげよう!!!

課題

N×Mの迷路の地図が与えられる。迷路は各マスごとに状態がある。その状態は4つある。

  • '#' : 壁
  • '.' : 通路
  • 'S' : スタート
  • 'G' : ゴール
迷路は通路と壁からできていて、1ターンに隣接する上下左右4マスの通路へ移動することができる。スタートからゴールまで移動するのに必要な最小のターン数を求めなさい。ただし、必ずスタートからゴールまで移動できるものとする。

入力

N M
a1,1 a2,1 ... aN,1
a1,2 a2,2 ... aN,2
   :
   :
   :
a1,M a1,M ... aN,M

出力

迷路のスタートからゴールまで移動するのに必要な最小のターン数を出力する。

sample

input

4 4
#S##
#...
#.##
G..#

output

4