A - 不完全迷路 Editorial /

Time Limit: 2 sec / Memory Limit: 291 MB

問題文

あなたは、道端で怪しげな迷路ジェネレーターを拾ってしまいました。 迷路ジェネレーターを動かすと、縦Hマス、横Wマスの迷路を自動で生成してくれます。 しかし、それには不具合があり、ゴールにたどり着くことのできない迷路を生成するようでした。 そこで、あなたは迷路を修正し、ゴールにたどり着くことのできるようにすることにしました。

迷路には、壁#と道.があり、スタートのマスSとゴールのマスGが1マスずつあります。 プレイヤーは、スタートのマスから移動を始め、隣接する縦横4マスの壁でないマスへ移動しながら、ゴールのマスを目指します。 あなたは、ここから壁のマスを 1マスのみ 道のマスに替えることで、ゴールにたどり着くことのできる迷路を作ることにしました。

ただし、ただ適当な壁を道に変えるでは面白くないと考えたあなたは、スタートからゴールまでの最短経路長が 最長 になるように壁を道に変えることにしました。

上記の操作を行った場合の、スタートからゴールまでの最短経路長を答えてください。

入力

H W
line_1
line_2
...
line_H
  • 1行目には、迷路の高さHと、迷路の幅W (2 \leq H, W \leq 298)が与えられます。
  • 2行目以降のH行には、W文字の文字列line_iが与えられます。各line_i (1 \leq i \leq H)は、#,.,S,Gで構成されており、#が壁、.が道、Sがスタート地点、Gがゴール地点を表します。

なお、S,Gは迷路の中に必ず1つづつ存在します。

与えられる迷路は、SからGへたどり着くことができず、必ず1マスの壁を道に替えるとゴールへたどりつけることが保証されています。

出力

修正した迷路のゴールまでの最短経路長を1行で出力してください。 出力の末尾には改行を入れること。

入力例1

6 8
S..#...#
##...#..
..###.##
........
.#######
.......G

出力例1

28

入力例2

5 6
#.S.#.
###...
...###
.#.#.G
.....#

出力例2

10

ループするような道もありえます

入力例3

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

出力例3

8

厚い壁もありえます

入力例4

6 8
S.......
########
...#....
.##..##.
...#.#..
.#.G#..#

出力例4

12

最初からS、Gどちらとも繋がっていない道もありえます

入力例5

7 8
.#......
S#.#.###
...#.#.#
###.#.G.
.....#..
..##.#.#
........

出力例5

14