← 返回题目列表

AtCoder · past20_j

J. 禁止的网格图案

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

问题陈述

有一个 N \times N 网格与 N 水平行和 N 垂直列。 (i, j) 表示单元格中 i从顶部开始的第行和 j左起第 列。最初,每个单元都被漆成黑色或白色;细胞 (i, j) 被漆成黑色,如果 S_{i, j} is #,如果 S_{i, j} is ..

您将重复选择一个单元格将其涂成黑色,以使网格满足以下条件:

  • 对于任何单元格 (x, y) 漆成白色,最多两个单元格 (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1) (不存在的除外)被漆成黑色。

至少需要多少次操作才能满足条件?

约束

  • 1 \leq N \leq 2000
  • S_{i, j} is . or #.

输入

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

N
S_{1, 1} S_{1, 2} \cdots S_{1, N}
S_{2, 1} S_{2, 2} \cdots S_{2, N}
\vdots
S_{N, 1} S_{N, 2} \cdots S_{N, N}

输出

在一行中打印答案。


示例输入 1

3
###
#.#
###

示例输出 1

1

细胞 (2, 2) 被漆成白色,所有四个相邻单元格被漆成黑色。通过重新绘制单元格 (2, 2) 黑色,网格满足条件。


示例输入 2

3
...
#.#
.#.

示例输出 2

1

通过重新绘制单元格 (2, 2) 黑色,网格满足条件。


示例输入 3

5
#####
#....
#.###
#...#
#####

示例输出 3

8

仅当所有白色单元格都重新绘制为黑色时,网格才满足条件。