分数: 500 点
问题陈述
有一个网格 N 行和 N 列。广场位于 i从顶部数第行和 j从左边算起的第列表示为正方形 (i, j).
网格中的每个方格都涂成白色或黑色。网格的信息由下式给出 N 字符串 S_1, S_2, \ldots, S_N。如果 j第一个字符 S_i is .,方形 (i, j) 被漆成白色;如果 j第一个字符 S_i is #,方形 (i, j) 被漆成黑色。
您将重新绘制一些方块,以满足以下两个条件:
- 对于每一行,以下条件成立:
- 存在一个整数 k 满意 0 \leq k \leq N 这样最左边的 k 该行的方块被漆成白色,其他方块被漆成黑色。
- 对于每一列,以下条件成立:
- 存在一个整数 k 满意 0 \leq k \leq N 这样最上面的 k 该列的方块被漆成白色,其他方块被漆成黑色。
求满足条件需要重新绘制的最小方块数。
约束
- 1 \leq N \leq 5000
- N 是一个整数。
- S_i 是一个长度为的字符串 N 组成
.和#.
输入
输入由标准输入按以下格式给出:
N S_1 S_2 \vdots S_N
输出
打印答案。
示例输入 1
3 ..# #.# .#.
示例输出 1
2
可以通过重新绘制方块来满足条件 (2, 1) 白色和方形 (3, 3) 黑色。
示例输入 2
5 ..#.# #..## ###.# .###. #....
示例输出 2
9