1949: #6030. 「雅礼集训 2017 Day1」矩阵
Time Limit: 1 Sec
Memory Limit: 256 MB
Submit: 24
Solved: 10
[
Submit][
Status][
Web Board]
Description
有一个 n×n n \times nn×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_nC1,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_nC1,C2,…,Cn。
你的任务是将整个矩阵变成全黑，如果能够办到，输出最少步数，否则输出 −1 -1−1。
Input
第一行一个整数 n nn。 接下来 n nn 行，每行 n nn 个字符表示整个矩阵。
Output
输出只有一行，一个整数表示答案。
Sample Input
2
#.
.#
Sample Output
3
HINT
对于 30% 30\%30% 的数据，n≤4 n \leq 4n≤4； 对于另外 20% 20\%20% 的数据，满足每一列都至少有一个黑色的格子； 对于 100% 100\%100% 的数据，1≤n≤1000 1 \leq n \leq 10001≤n≤1000。
【分析】
首先可以发现一点，只要这个图中存在黑点，那么一定存在操作能使这个图变成全黑，所以只有图中不存在黑点的时候答案才是-1。
在考虑完-1之后，需要考虑的就是在一定存在答案的情况下，怎么判断最优解，
首先我们可以想到，要使得整个图都变成黑色的，那么模拟一下可以发现，不管如何操作，不管是否优先把某一行填满，中途总会有一行先变成黑色，当存在一行全是黑色的时候，后面的步骤就是用这一行依次去填满还没有满的每一列。
对于每一列，最少用一步才能让这一列都变成黑色，
所以我们考虑优先把某一行填满，剩下的步骤就是用这一行去填满所有未满的列了。
对填满某一行需要的步骤，就是这行中白点的数量，如果这行中没有白点，或者不存在某一种操作能让这一行中多出一个黑点，也就是对当前i行没有i列存在黑点，就需要多一步
【代码】
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
char a[1100][1100];
int vis[1100]={0};
int main()
{
int n;scanf("%d",&n);
for (int i=0;i<n;i++) scanf("%s",a[i]);
int flag=1;
int ans=0;
for (int i=0;i<n;i++)
{
int t=0;
for (int j=0;j<n;j++)
{
if (a[i][j]=='#') flag=0;
if (a[j][i]=='.') t=1;
if (a[j][i]=='#') vis[i]=1;
}
ans+=t;
}
if (flag){printf("-1\n");return 0;}
int sum=0x3f3f3f3f;
for (int i=0;i<n;i++)
{
int t=0;
for (int j=0;j<n;j++)
if (a[i][j]=='.')
t++;
if (t==n||!vis[i]) t++;
sum=min(sum,t);
}
printf("%d\n",ans+sum);
return 0;
}
