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