Score : $500$ points

问题描述

有一个城镇被划分为一个 $H$ 行和 $W$ 列的网格。若第 $i$ 行（从上数）、第 $j$ 列（从左数）处的单元格记为 $S_{i,j}$，当 $S_{i,j}$ 为.时，表示这是一个可通行的空间；当 $S_{i,j}$ 为#时，则表示这是一个障碍物。

高桥要从他的家前往鱼市。他的家位于左上角的单元格，而鱼市则位于右下角的单元格。

高桥可以向上、下、左、右移动一个单元格到达一个可通行的区域。他不能离开城镇范围，并且也不能进入障碍物所在单元格。然而，他的体力允许他用一拳摧毁任意选择的一个 $2\times 2$ 单元格大小的正方形区域内的所有障碍物，使得这些单元格变为可通行。

请计算高桥至少需要多少次出拳才能到达鱼市。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a town divided into a grid of cells with $H$ rows and $W$ columns. The cell at the $i$-th row from the top and $j$-th column from the left is a passable space if $S_{i,j}$ is . and a block if $S_{i,j}$ is #.

Takahashi will go from his house to a fish market. His house is in the cell at the top-left corner, and the fish market is in the cell at the bottom-right corner.

Takahashi can move one cell up, down, left, or right to a passable cell. He cannot leave the town. He cannot enter a block, either. However, his physical strength allows him to destroy all blocks in a square region with $2\times 2$ cells of his choice with one punch, making these cells passable.

Find the minimum number of punches needed for Takahashi to reach the fish market.

Constraints

• $2 \leq H,W \leq 500$
• $H$ and $W$ are integers.
• $S_{i,j}$ is . or #.
• $S_{1,1}$ and $S_{H,W}$ are ..

Input

Input is given from Standard Input in the following format:

$H$ $W$

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

$\vdots$

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

1

He can reach the fish market by, for example, destroying the blocks in the square region with $2\times 2$ cells marked * below.

..#..
#.**#
##**#
#.#.#
..#..```

It is not required that all of the $2\times 2$ cells in the region to punch are blocks.
## Sample Input 2

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

## Sample Output 2

0

He can reach the fish market without destroying blocks, though he has to go a long way around.
## Sample Input 3

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

## Sample Output 3

5

 update @ 2024/3/10 09:29:53