#6030. 「雅礼集训 2017 Day1」矩阵
题目描述
有一个 n×n 的矩阵，每个位置 (i,j) 如果是 . 表示为白色，如果是 # 表示为黑色。
初始时，每个位置可以是黑色或白色的，(i,j) 位置的值会作为 ai,j 给你。
现在有一种操作，选择两个整数 i,j∈[1,n]，记 (i,1),(i,2),…,(i,n) (i, 1), (i, 2)的颜色为 C1,C2,…Cn ，将 (1,j),(2,j),…,(n,j) 的颜色赋为 C1,C2,…,Cn 。
你的任务是将整个矩阵变成全黑，如果能够办到，输出最少步数，否则输出 −1。
输入格式
第一行一个整数 n nn。 接下来 n nn 行，每行 n nn 个字符表示整个矩阵。
输出格式
输出只有一行，一个整数表示答案。
样例
样例输入 1
2
#.
.#样例输出 1
3样例输入 2
2
..
..样例输出 2
-1数据范围与提示
对于 30% 的数据，n≤4
对于另外 20%的数据，满足每一列都至少有一个黑色的格子；
对于 100% 的数据，1≤n≤1000
很巧妙地思路 应该是贪心吧。。
首先我们模拟一下可以发现
想要把整张图涂黑 一定是先涂黑一行之后 再涂整张图
涂黑一列的代价最小只能为1
那么我们可以想办法先用最少的步数涂黑一行
再用这一行去涂改其他列
涂改一行的最少步数 无非就是这一行的白点数
但是有一种特殊情况
像这样 (3,3) 这个位置不可能一次就涂成黑色
即你用的 第i行 对应的 第i列 没有一个黑点
这时候需要多加一步
先用第3行对第3列染色
然后再用 第1行 或 第2行 把(3,3)这个位置涂黑
无论是 第1行 还是 第2行 (3,1)和(3,2) 一定会又变成白色 这不影响我们的程序
因为中间那一步一定会被后来的一步给覆盖
这就是特殊情况多加一步
之后统计还有多少列 存在白点 用全黑的一行涂改就好了
1 #include <cstdio> 2 #include <cctype> 3 4 const int MAXN=1010; 5 6 int n; 7 8 char s[MAXN]; 9 10 int map[MAXN][MAXN],h[MAXN],l[MAXN]; 11 12 bool flag; 13 14 inline void read(int&x) { 15 int f=1;register char c=getchar(); 16 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 17 for(;isdigit(c);x=x*10+c-48,c=getchar()); 18 x=x*f; 19 } 20 21 inline int min(int a,int b) {return a<b?a:b;} 22 23 inline void running() { 24 int ans=0x3f3f3f3f; 25 for(int i=1;i<=n;++i) 26 ans=min(ans,n-h[i]+(l[i]==0));//用最少的步数将一行转化成黑色 27 for(int i=1;i<=n;++i) 28 if(l[i]!=n) ++ans;//还有哪列没有涂黑 29 printf("%d ",ans); 30 return; 31 } 32 33 int hh() { 34 read(n); 35 for(int i=1;i<=n;++i) { 36 scanf("%s",s+1); 37 for(int j=1;j<=n;++j) 38 if(s[j]=='#') { 39 flag=true; 40 ++h[i]; 41 ++l[j]; 42 } 43 } 44 if(!flag) printf("-1 "); 45 else running(); 46 return 0; 47 } 48 49 int sb=hh(); 50 int main(int argc,char**argv) {;}