← 返回题目列表

AtCoder · abc442_f

F. 对角分离 2

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

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