题目描述

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

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

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

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

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

题面

有一个城镇被划分为H行和W列的单元格网格。
如果 $S_i,_j$ 是' . '，则为道路；如果 $S_i,_j$ 为' # '，则为障碍物。

高桥将从家里去鱼市。他的房子在左上角的方格，鱼市在右下角的方格。

高桥可以从一个单元格向上、向下、向左或向右移动到可通过的单元格。他不能离开小镇，也不能进入街区。
但是，他可以一次摧毁一个 2$\times$2 正方形区域中的所有障碍物，使这个区域可以通过。

找到高桥进入鱼市所需的最少次数。

数据范围

• 2 $\le H,W \le 500$
• $H,W$ 是整数
• $S_i,_j$ 只会是 ' . ' 或 ' # '
• $S_1,_1$ 和 $S_H,_W$ 都是 ' . '

样例解释

1. 通过打破 $S_3,_2 S_3,_3 S_4,_2 S_4,_3$ 这个2$\times$2 的正方形区域，高桥可以顺利到达鱼市。
2. 高桥不需要打破障碍物就可以顺利到达鱼市，尽管他需要绕路。

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

1

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

0

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

5

提示

制約

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

Sample Explanation 1

例えば、以下の \* で表す $2\times\ 2$ の区画にある塀を破壊すると魚屋にたどり着くことができます。 ..#.. #.\*\*# ##\*\*# #.#.# ..#.. 破壊対象の $2\ \times\ 2$ の区画の全てが塀である必要はありません。

Sample Explanation 2

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