题目描述

有一个 $H$ 行 $W$ 列的网格。从上数第 $i$ 行，从左数第 $j$ 列的格子记作 $(i, j)$。若 $S_{i,j}$ 是 . （点）则 $(i, j)$ 是路，若 $S_{i,j}$ 是 # 则 $(i, j)$ 是墙。

高桥要从 $(1, 1)$ 走到 $(H, W)$。他可以往上下左右走，但不能走到墙格子也不能走出网格。不过高桥力气很大，他一拳可以把网格里任意一个 $2\times 2$ 区域内的墙全部摧毁，变成路。

高桥要走到格子 $(H, W)$ 至少要打几拳？ 限制

• $2 \le H, W \le 500$
• $(1, 1)$ 和 $(H, W)$ 是路。

输入格式

$H$ $W$

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

$\vdots$

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

输出格式

输出答案。

5 5

..#..

#.#.#

##.##

#.#.#

..#..

1

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

0

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

5