问题陈述
有一个 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
仅当所有白色单元格都重新绘制为黑色时,网格才满足条件。