← 返回题目列表

AtCoder · abc213_e

H. 更强的高桥

中文机器翻译题面 查看原题

分数: 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