Stronger Takahashi

题目描述

有一个小镇被划分成 $H$ 行 $W$ 列的网格。位于从上数第 $i$ 行、从左数第 $j$ 列的格子如果 $S_{i,j}$ 为 $.$ 则为可通行的空间，如果 $S_{i,j}$ 为 # 则为障碍。 Takahashi 将从他家前往鱼市场。他的家位于左上角的格子，鱼市场位于右下角的格子。 Takahashi 可以向上、下、左、右移动一格到达可通行的格子。他不能离开小镇。 他也不能进入障碍。不过，他的体力允许他用一拳摧毁任意选择的一个 $2\times 2$ 方形区域内的所有障碍，使这些格子变为可通行。 求 Takahashi 到达鱼市场所需的最小拳数。

输入格式

输入从标准输入按以下格式给出： $H$ $W$ $S_{1,1} \ldots S_{1,W}$ $\vdots$ $S_{H,1} \ldots S_{H,W}$

输出格式

输出答案。

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}$ 为 $.$。例如，他可以通过摧毁下方用 $*$ 标记的 $2\times 2$ 区域中的障碍到达鱼市场。

被击打的 $2\times 2$ 区域内不需要全部是障碍。
他也可以不摧毁任何障碍就到达鱼市场，尽管那样他需要绕很远的一圈。

标签: AtCoder|abc213E

来源

AtCoder|abc213E