P5744: 矩阵
传统题
1.000s
时间限制
256MB
内存限制
2 提交
1 解决
【题目描述】
有一个
n×n n \times n n×n 的矩阵，每个位置
(i,j) (i, j) (i,j) 如果是.表示为白色，如果是#表示为黑色。
初始时，每个位置可以是黑色或白色的，
(i,j) (i, j) (i,j) 位置的值会作为
ai,j a_{i, j} ai,j 给你。
现在有一种操作，选择两个整数
i,j∈[1,n] i, j \in [1, n] i,j∈[1,n]，记
(i,1),(i,2),…,(i,n) (i, 1), (i, 2), \ldots, (i, n) (i,1),(i,2),…,(i,n) 的颜色为
C1,C2,…Cn C_1, C_2, \ldots C_n C1,C2,…Cn，将
(1,j),(2,j),…,(n,j) (1, j), (2, j), \ldots, (n, j) (1,j),(2,j),…,(n,j) 的颜色赋为
C1,C2,…,Cn C_1, C_2, \ldots, C_n C1,C2,…,Cn。
你的任务是将整个矩阵变成全黑，如果能够办到，输出最少步数，否则输出
−1 -1 −1。
【输入】
第一行一个整数 n n n。
接下来 n n n 行，每行 n n n 个字符表示整个矩阵。
【输出】
【提示】
对于 30% 30\% 30% 的数据，n≤4 n \leq 4 n≤4；
对于另外 20% 20\% 20% 的数据，满足每一列都至少有一个黑色的格子；
对于 100% 100\% 100% 的数据，1≤n≤1000 1 \leq n \leq 1000 1≤n≤1000。