- 给定一个(n imes n)的黑白矩阵。
- 一次操作可以用某一行的格子去覆盖某一列的格子。
- 问至少多少步能够把整个矩阵染黑。
- (nle1000)
解题思路
先判无解，当且仅当所有格子为白。
考虑我们必然是先集中力量把某一行全部染黑，然后再用这一行把所有不是全黑的列染黑，整体分成两部分。
枚举选择第(i)行，如果一开始原本就有某一行的第(i)列为黑，我们可以利用这一行把所有第(i)行为白的列的第(i)行都染黑；如果没有，我们任选一个原本有黑的行去覆盖第(i)列，必然能产生第(i)列为黑的行。两种情况实际上只差一步。
然后我们发现一开始就全黑的列肯定不会去修改，而一开始不是全黑的列我们在之前的操作中肯定不可能把它染全黑，因此这部分的总操作次数实际上是固定的。
然后两部分拼起来就好了，求解答案的过程复杂度实际上只有(O(n))。
代码：(O(n^2))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000
using namespace std;
int n,c[N+5],p[N+5];char s[N+5][N+5];
int main()
{
RI i,j,t=0;for(scanf("%d",&n),i=1;i<=n;++i) scanf("%s",s[i]+1);
for(i=1;i<=n;++i) for(j=1;j<=n;++j) s[i][j]=='#'&&(t=1);if(!t) return puts("-1"),0;//如果全白
for(i=1;i<=n;++i) for(j=1;j<=n;++j) s[i][j]=='#'&&(++c[i],p[j]=1);//统计每行原本黑格子数，每列是否有黑格子
for(t=0,j=1;j<=n;++j) {for(i=1;i<=n&&s[i][j]=='#';++i);i>n&&++t;}//统计原本全黑的列数
RI w=1e9;for(i=1;i<=n;++i) w=min(w,!p[i]+(n-c[i])+(n-t));return printf("%d
",w),0;//枚举染全黑的行统计答案
}