2072 - 迷路脱出中のKamba君

問題

Kamba君は奥行き $H$, 幅 $W$ の2D迷路に閉じ込められてしまいました。迷路は $.$（通れる）と $!$（壁）で構成されており、スタート地点 $S$ からゴール地点 $G$ まで、以下のルールで移動できるものとします。

• 1つのマスを移動するのにかかるコストは $1$ である。
• 移動できる方向は上、右上、右、右下、下、左下、左、左上、の8方向である。

このとき、ゴールに到達するために必要な最小コストを求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$ 
$c_{1,1}$$c_{1,2}$$...$$c_{1,W}$
$c_{2,1}$$c_{2,2}$$...$$c_{2,W}$
$:$
$:$
$c_{H,1}$$c_{H,2}$$...$$c_{H,W}$

1行目に整数 $H$ と $W$ が与えられる。
2行目以降に迷路の状態 $c_{i,j}$ が与えられる。$(1 \leq i \leq H, 1 \leq j \leq W)$

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $2 \leq H, W \leq 740$
• $c_{i,j}$ は $.$, $!$, $S$, $G$ のいずれかである。$(1 \leq i \leq H, 1 \leq j \leq W)$
• $S$ および $G$ はそれぞれ1つだけ与えられる。
• 迷路の範囲外（$1 \leq x \leq W, 1 \leq y \leq H$ を満たさない座標 $(x,y)$ ）はすべて壁として扱う。
• この問題では、必ず $S$ から $G$ に必ずたどり着ける。

入出力例

入力例1

5 5
S....
.!!!.
.!...
.!.!.
.!G..

出力例1

7

下のようなルートが最短になります。
!! !! !! !! !! !! !!
!! 00 01 02 03 .. !!
!! .. !! !! !! 04 !!
!! .. !! .. 05 .. !!
!! .. !! 06 !! .. !!
!! .. !! 07 .. .. !!
!! !! !! !! !! !! !!

入力例2

7 5
...!.
.!!..
.!!!.
.!S!.
.!!.!
!.!!!
!!..G

出力例2

14

下のようなルートが最短になります。
!! !! !! !! !! !! !!
!! .. 06 05 !! .. !!
!! 07 !! !! 04 .. !!
!! 08 !! !! !! 03 !!
!! 09 !! 00 !! 02 !!
!! 10 !! !! 01 !! !!
!! !! 11 !! !! !! !!
!! !! !! 12 13 14 !!
!! !! !! !! !! !! !!

※ スペースを2つ以上入れることができないので、$.$ を $..$、 $!$ を $!!$ にしています。