102134: [AtCoder]ABC213 E - Stronger Takahashi
Description
Score : $500$ points
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
Input
题意翻译
### 题面 有一个城镇被划分为H行和W列的单元格网格。 如果 $S_i,_j$ 是' . '，则为道路；如果 $S_i,_j$ 为' # '，则为障碍物。 高桥将从家里去鱼市。他的房子在左上角的方格，鱼市在右下角的方格。 高桥可以从一个单元格向上、向下、向左或向右移动到可通过的单元格。他不能离开小镇，也不能进入街区。 但是，他可以一次摧毁一个 2$\times$2 正方形区域中的所有障碍物，使这个区域可以通过。 找到高桥进入鱼市所需的最少次数。 ### 数据范围 - 2 $\le H,W \le 500$ - $H,W$ 是整数 - $S_i,_j$ 只会是 ' . ' 或 ' # ' - $S_1,_1$ 和 $S_H,_W$ 都是 ' . ' ### 样例解释 1. 通过打破 $S_3,_2 S_3,_3 S_4,_2 S_4,_3$ 这个2$\times$2 的正方形区域，高桥可以顺利到达鱼市。 2. 高桥不需要打破障碍物就可以顺利到达鱼市，尽管他需要绕路。Output
问题描述
有一个由H行和W列组成的格子小镇。从上数第i行、从左数第j列的格子是一个可以通过的空间，如果$S_{i,j}$是.；如果$S_{i,j}$是#，则是一个障碍物。
高桥要从他的房子去鱼市。他的房子在左上角的格子，鱼市在右下角的格子。
高桥可以向上、下、左、右移动到一个可以通过的格子。他不能离开小镇。 他也不能进入障碍物。然而，他的体力允许他用一拳摧毁一个由他选择的2x2个单元格组成的正方形区域中的所有障碍物，使这些单元格可以通过。
找出高桥到达鱼市所需的最少拳击次数。
限制条件
- $2 \leq H,W \leq 500$
- H和W是整数。
- $S_{i,j}$是
.或#。 - $S_{1,1}$和$S_{H,W}$是
.。
输入
输入格式如下，从标准输入给出：
$H$ $W$
$S_{1,1} \ldots S_{1,W}$
$\vdots$
$S_{H,1} \ldots S_{H,W}$
输出
打印答案。
样例输入1
5 5 ..#.. #.#.# ##.## #.#.# ..#..
样例输出1
1
他可以通过，例如，摧毁下面标记为*的2x2正方形区域中的障碍物来到达鱼市。
..#..
#.**#
##**#
#.#.# ..#..
不需要被拳击区域的2x2个单元格都是障碍物。
样例输入2
5 7 ....... ######. ....... .###### .......
样例输出2
0
他可以在不摧毁障碍物的情况下到达鱼市，虽然他需要绕很长的路。
样例输入3
8 8 .#######
########
########
########
########
########
########
#######.
样例输出3
5