← 返回题目列表

AtCoder · mujin_pc_2017_b

B. 行到列

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

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

方块颜色的过渡如下图所示:

6a0314bb2b1073694a7ef5a062e77b13.png

示例输入 2

2
..
..

示例输出 2

-1

示例输入 3

2
##
##

示例输出 3

0

示例输入 4

3
.#.
###
.#.

示例输出 4

2

示例输入 5

3
...
.#.
...

示例输出 5

5