分数: 500 点
问题陈述
有一个城镇,分为网格单元格, H 行和 W 列。牢房位于 i从顶部开始的第行和 j从左边算起的第列是一个可以通过的空间,如果 S_{i,j} is . 和一个块 if S_{i,j} is #.
高桥将从他家前往鱼市。他的房子在左上角的牢房里,鱼市场在右下角的牢房里。
Takahashi 可以将一个单元格向上、向下、向左或向右移动到可通过的单元格。他不能离开这个城镇。 他也不能进入一个街区。然而,他的体力允许他用以下方法摧毁一个正方形区域内的所有方块: 一拳打出 2\times 2 自己选择的细胞,让这些细胞通过。
求高桥到达鱼市所需的最少拳头次数。
约束
- 2 \leq H,W \leq 500
- H 和 W 是整数。
- S_{i,j} is
.or#. - 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
他可以通过以下方式到达鱼市:例如,用以下方法摧毁正方形区域中的方块: 2\times 2 单元格已标记 * 如下。
..#.. #.**# ##**# #.#.# ..#..
不要求所有 2\times 2 要打孔的区域中的单元格是块。
示例输入 2
5 7 ....... ######. ....... .###### .......
示例输出 2
0
他可以在不破坏方块的情况下到达鱼市,尽管他必须绕很远的路。
示例输入 3
8 8 .####### ######## ######## ######## ######## ######## ######## #######.
示例输出 3
5