RERE
森の中に住む方向音痴の山田君は、地図がないと森の中を彷徨うことができない。
そこで山田君は、知人のKOMONOSANに、自宅付近の森の地図を描いてもらうことにした。
困ったことに、この森の地形は、数日前から一日ごとに変化し続けている。
そして山田君は花粉症なので、木がある方向に進んだり、木を力ずくで突破したりすることができない。
KOMONOSANは魔法使いである。
KOMONOSANの使う魔法の種類は様々であり、山田君は、その中の「どんな地形からでも地図が作れる魔法」に着目し、
KOMONOSANに依頼を頼んだ。
これで毎日KOMONOSANに地図を作ってもらうことで、山田君は自宅から、毎日森の中にランダムで生成されるGAME CENTERに通い詰めることができる。
しかし、時間を無駄にしたくない山田君は、より速くGAME CENTERに到着したいと思い、毎朝KOMONOSANからもらった地図から、
GAME CENTERへ最短で行ける道を探そうと試みた。
だが、道を一つ一つたどっていくのは時間がかかりすぎると気づいた山田君は、頭のいいあなたに山田君の家から、GAME CENTERへの最短で行ける道のりを探してほしい、と頼んできた。
山田君からは、KOMONOSANが作った地図が与えられた。
どうか山田君のかわりに、GAME CENTERへ最低何歩で行けるかを求めてほしい。
入力
H W 横 W 文字、縦 H 行からなる文字列 M
1 行目に整数 H W が与えられる。
2 行目に文字列 M が与えられる。
山田君の自宅は「S」、GAME CENTERは「G」、木々は「#」で表される。
何もないところは「.」で表される。
※ただしKOMONOSANの調子が悪いときは、GAME CENTERの場所はおろか、山田君の自宅の位置さえ地図に転写できない時もある。(そのときは悲しい)
出力
文字列Mに含まれる「S」の座標から、文字列Mに含まれる「G」の座標にたどり着くまでの最短の距離を出力せよ。
到達できない場合は、「kanasi」と出力せよ。
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- 0 ≦ W,H ≦ 20
入出力例
入力例1
9 6 S...#. .....# ...... ...... ...... ...... .....G #....# .#..#.
出力例1
11
解説
一例だが、S地点から下に6歩、そこから右に5歩歩くことで、森の中のGAME CENTERに着ける。
入力例2
9 11 S#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..G#.#. .#.#####.#. .#.......#. .#########. ...........
出力例2
58
入力例3
6 11 G.#..#..#.. ..#..#..#.. ..#..#..### ..#..#..#S. ..#..#..#.. ..#..#..#..
出力例3
kanasi
解説
この場合は山田君の自宅が木で囲まれてしまっているため、GAME CENTERには到達不可能となる。