[AdditionalFile6030.zip](file://AdditionalFile6030.zip?type=additional_file)

#6030. 「雅礼集训 2017 Day1」矩阵

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

有一个 $n \times n$ 的矩阵，每个位置 $(i, j)$ 如果是 . 表示为白色，如果是 # 表示为黑色。

初始时，每个位置可以是黑色或白色的，$(i, j)$ 位置的值会作为 $a_{i, j}$ 给你。

现在有一种操作，选择两个整数 $i, j \in [1, n]$，记 $(i, 1), (i, 2), \ldots, (i, n)$ 的颜色为 $C_1, C_2, \ldots C_n$，将 $(1, j), (2, j), \ldots, (n, j)$ 的颜色赋为 $C_1, C_2, \ldots, C_n$。

你的任务是将整个矩阵变成全黑，如果能够办到，输出最少步数，否则输出 $-1$。

输入格式

第一行一个整数 $n$。 接下来 $n$ 行，每行 $n$ 个字符表示整个矩阵。

输出格式

输出只有一行，一个整数表示答案。

样例 1

输入

2
#.
.#

输出

3

样例 2

输入

2
..
..

输出

-1

数据范围与提示

对于 $30\%$ 的数据，$n \leq 4$；
对于另外 $20\%$ 的数据，满足每一列都至少有一个黑色的格子；
对于 $100\%$ 的数据，$1 \leq n \leq 1000$。