← 返回题目列表

AtCoder · arc112_d

D. 滑冰

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

分数: 600 点

问题陈述

高桥在一个溜冰场上,其中包括 H 行和 W 方格列。 让 (r, c) 表示 r从北数第 行, c从西数第 3 列。 每个方格都是冰或地面; (r, c) 被接地,如果 S_{r, c} is # 和冰如果 S_{r, c} is .。 溜冰场周围有围墙。

当高桥站在溜冰场上不动时,他可以开始向东、西、南或北移动。 当他开始移动后,他会继续朝同一个方向移动,直到撞到墙壁或者被撞倒。 on 地面方格(除了他开始移动的方格之外)。

我们说溜冰场对于 (r, c) 当满足以下条件时:

  • 有一系列动作从 (r, c),站着不动,并且 通过 每个方块。 (不需要在每个方格都停下来。)

Takahashi 希望将一定数量的冰块更改为地面块,以便溜冰场对每个块都有效。 他至少需要改变多少个方格?

约束

  • 2\le H,W \le 1000
  • S_{r,c} is # or ..

输入

输入由标准输入按以下格式给出:

H W
S_{1,1}\dots S_{1,W}
\vdots
S_{H,1}\dots S_{H,W}

输出

打印出使每个方格的溜冰场高效所需的最少更改次数。


示例输入 1

3 9
.........
.........
.........

示例输出 1

1

最初,不可能从 (1, 1) 并通过 (2, 2)。 实现该目标的一种方法是按如下方式更改溜冰场:

.........
........#
.........

示例输入 2

10 10
..........
#...#.....
..........
..........
..........
....#.....
.#......#.
..........
..........
..........

示例输出 2

6