更强壮的高桥

题目描述

有一座被分割成 $H$ 行 $W$ 列网格的小镇。从上数第 $i$ 行、从左数第 $j$ 列的格子,若 $S_{i,j}$ 为 .,则是可通行的空地;若 $S_{i,j}$ 为 #,则是墙壁。

高桥君要从家前往鱼市。他的家在左上角的格子,鱼市在右下角的格子。

高桥君可以向上、下、左、右移动一格到可通行的格子。他不能离开小镇。 也不能进入墙壁。但是,凭借他的体力,他可以用一拳摧毁任意一个 $2\times 2$ 正方形区域内的所有墙壁,使这些格子变得可通行。

求高桥君到达鱼市所需的最小出拳次数。

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

• $2 \le H, W \le 500$
• $H$ 和 $W$ 是整数
• $S_{i,j}$ 为 . 或 #
• $S_{1,1}$ 和 $S_{H,W}$ 均为 .