配点 : $500$ 点

問題文

$H$ 行 $W$ 列の格子状の区画に区切られた街があります。上から $i$ 行目、左から $j$ 列目の区画は、$S_{i,j}$ が . のとき道、# のとき塀です。

高橋君は自分の家から魚屋に買い物に行くことにしました。高橋君の家は街の左上隅の区画にあり、魚屋は街の右下隅の区画にあります。

高橋君は、自分がいる区画から上下左右に隣接する道の区画に移動することができます。街の外に出ることはできません。 塀の区画に移動することはできませんが、高橋君は非常に腕力が強いため、パンチを $1$ 回繰り出すことで任意の $2\times 2$ の区画内の塀を壊して道にすることができます。

高橋君が魚屋にたどり着くためには、最低何回パンチを繰り出せばよいか求めてください。

制約

• $2 \leq H,W \leq 500$
• $H,W$ は整数
• $S_{i,j}$ は . または #
• $S_{1,1}$ と $S_{H,W}$ は .

入力

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

$H$ $W$

$S_{1,1} \ldots S_{1,W}$

$\vdots$

$S_{H,1} \ldots S_{H,W}$

出力

答えを出力せよ。

5 5
..#..
#.#.#
##.##
#.#.#
..#..

1

例えば、以下の * で表す $2\times 2$ の区画にある塀を破壊すると魚屋にたどり着くことができます。

..#..
#.**#
##**#
#.#.#
..#..

破壊対象の $2 \times 2$ の区画の全てが塀である必要はありません。

5 7
.......
######.
.......
.######
.......

0

遠回りが必要ですが、塀を破壊することなく魚屋にたどり着くことができます。

8 8
.#######
########
########
########
########
########
########
#######.

5