#`. 强壮的高桥

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一个 $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)$ 至少要打几拳？限制

$H$ $W$

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

$\vdots$

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

输出答案。

5 5

..#..

#.#.#

##.##

#.#.#

..#..

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

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