#P9040. [2017年备战省选]矩阵

[2017年备战省选]矩阵

题目描述

给定一个 n×nn\times n 矩阵,每个格子是黑色或白色。字符「#」表示黑色,字符「.」表示白色。

一次操作选择 i,j∈[1,n]i,j\in[1,n],读取第 ii 行从左到右的颜色 C1,…,CnC_1,\ldots,C_n,再把第 jj 列从上到下的颜色赋为 C1,…,CnC_1,\ldots,C_n。

求把整个矩阵变成全黑所需的最少操作数。如果无法做到,输出 −1-1。

输入格式

第一行一个整数 nn。接下来 nn 行,每行 nn 个字符,表示初始矩阵。

输出格式

输出一行一个整数,表示答案。

样例 1

2
#.
.#
3

样例 2

2
..
..
-1

数据范围

  • 对于 30%30\% 的数据,n≤4n\le4。
  • 对于另外 20%20\% 的数据,每列至少有一个黑色格子。
  • 对于所有数据,1≤n≤10001\le n\le1000。

原 PDF 题面