Ice Maze

Time Limit : 1 sec, Memory Limit : 65536 KB

氷の迷路

四角のマスを縦横にならべた長方形の迷路があります。この迷路では東西南北の隣接するマスへ移動しながら、スタートのマスSを出発し、ゴールのマスGを目指します。マスの種類には、平原、山、氷の3種類があります。SとGは、平原のマスに置かれています。平原のマスには移動できますが、山のマスには移動できません。氷のマスは移動できますが、条件によって氷が割れ動けなくなります。

  • 氷のマスは東西南北に隣接するもの全体でひとつの塊として扱われます。
  • 氷の塊のなかで、マスの個数の半分より多くのマスに移動すると、塊全体が割れます。

例えば、図1は与えられた迷路の最短経路のステップ数で11であることを示しています。


図1

しかし、図2のように氷のマスを通って近道をしようとすると、大きさが6の氷の塊に対する4回目の移動後に動けなくなってしまいGには到達できません。

図2

このような迷路の情報を入力とし、SからGまでの最短経路のステップ数を求めるプログラムを作成してください。マスの種類はそれぞれ以下の文字で表されます:

文字(半角) マスの種類
. (ピリオド) 平原
#(シャープ)
X

与えられる迷路は必ず解けるものとします。迷路はその東西方向のマスの数x、南北方向のマスの数yとx×y個の文字として与えられます。x、yはともに2以上12以下とします。

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下のとおりです。

1行目 x y (整数 整数;半角空白区切り)
2行目 迷路の1行目の情報(長さxの半角英文字列)
:
y+1行目 迷路のy行目の情報

出力

入力データセットごとに、最小のステップ数を出力します。

入力例

5 5
.X.S.
.X#..
.XX##
.#XG.
..X..
7 3
SXX.XXG
X.#.#X.
XXX.XX#
4 4
S...
X.X.
GX..
...X
10 10
..XXXXX.XX
.X.#.#X.XX
SX.#X.X..X
#X.##.X.XX
..XXXX#.XX
##.##.##XX
....X.XX#X
.##X..#X#X
....XX#..X
...#XXG..X
0 0

出力例

11
10
10
33

Source: PC Koshien 2011, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2011
(revised version)
http://www.pref.fukushima.jp/pc-concours/