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

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一个 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
#.
.#

样例输出 1

3

样例输入 2

2
..
..

样例输出 2

-1

数据范围与提示

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