分数: 1300 点
问题陈述
有一个正方形网格, N 垂直行和 N 水平列。 我们将把正方形表示为 i从顶部开始的第行和 j从左起第 列为 (i,\ j).
最初,每个方块要么是白色,要么是黑色。
网格的初始颜色作为字符提供给您 a_{ij},排列成正方形。
如果正方形 (i,\ j) 是白色的, a_{ij} is .。如果是黑色的话 a_{ij} is #.
您正在开发一个可以重新绘制网格的机器人。 它可以重复执行以下操作:
- 选择两个整数 i, j (1 ≤ i,\ j ≤ N)。记住方块的颜色 分别是 (i,\ 1), (i,\ 2), ..., (i,\ N) as c_1, c_2, ..., c_N。然后,重新绘制正方形 (1,\ j), (2,\ j), ..., (N,\ j) 与颜色 c_1, c_2, ..., c_N。
你的目标是将所有方块变成黑色。 确定是否可能,如果答案是肯定的,则找到实现它所需的最少操作次数。
约束
- 2 ≤ N ≤ 500
- a_{ij} 是
.or#.
部分分数
- 在测试集中值得 300 点, N ≤ 3.
输入
输入由标准输入按以下格式给出:
N
a_{11}...a_{1N}
:
a_{N1}...a_{NN}
输出
如果可以将所有方块变成黑色,请打印实现该目标所需的最少操作数。
如果不可能,则打印 -1 。
示例输入 1
2 #. .#
示例输出 1
3
例如,执行如下操作:
- 选择 i = 1, j = 2.
- 选择 i = 1, j = 1.
- 选择 i = 1, j = 2.
方块颜色的过渡如下图所示:
示例输入 2
2 .. ..
示例输出 2
-1
示例输入 3
2 ## ##
示例输出 3
0
示例输入 4
3 .#. ### .#.
示例输出 4
2
示例输入 5
3 ... .#. ...
示例输出 5
5