题目链接

https://codeforces.com/problemset/problem/426/D

解题思路

首先应当得出点结论：

  1. 数据规模小。
  2. 如果01矩阵中所有0的连通块以及1的连通块都是矩阵的话，那么其实可以确定01矩阵的每一行与下一行的关系，要么这两行的元素全部相等，要么就全部相反。
  3. ** 当 n<=k 时，可以枚举第一列的01状态，其他各行都根据第一列**的状态进行变换操作以保证所有01连通块都为矩阵。同时注意，枚举的是第一列的状态，因为是行数小于等于k，k又小于等于10，2^10是可行的，但是列数最多为100，2^100是不可行的。当然，这只是其中一个很片面的原因，望自行理解。
  4. 当 n>k 时，意味着最多进行k次变换，最多将这k次变换分别施加到不同行，即最多施加到k行，由于n>k，所以至少有一行是没有进行过变换的。枚举没进行过变换的行，其他各行以此行为标准进行变换操作以保证所有01连通块都为矩阵。同时注意，只需要枚举一行就行，尽管可能有多行不会发生变换操作，但是不会发生变换操作这一过程会在代码中隐式包括了，望自行理解。
  5. 注意，两种情况的讨论都是在确定某一行/列的状态为标准的情况下，对每一行/列进行变换操作以保证所有01连通块都为矩阵。尽管这句话说了两遍了，但还是想重复一遍整体思想。
  6. 这不禁让我想到了一个题： 费解的开关。说实话，要不是这道题当列题学的，根本想不到是个二进制枚举，通过下一行去维护上一行的状态。是我，不是你们……

AC代码

#include<bits/stdc++.h>

using namespace std;
const int N=110;
const int INF=0x3f3f3f3f;

int a[N][N],n,m,k,ans=INF;

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)//从0开始方便状压移位 
    scanf("%d",&a[i][j]);

    if(n<=k)
    {
        for(int t=0;t<(1<<n);t++)//枚举第一行的状态 
        {
            int tmp=0;
            for(int j=0;j<m;j++)//遍历列 
            {
                int cnt=0;
                for(int i=0;i<n;i++)//遍历行 
                if(a[i][j]==(t>>i&1)) cnt++;//变成与第一行状态需要的操作次数 
                tmp+=min(cnt,n-cnt);//可以选择变成相反的或者变成相同的，要选当然是选变换操作次数少的//太细节了！！ 
            }
            ans=min(ans,tmp);//记录所有方案中最小的操作次数 
        }
    }
    else
    {
        for(int t=0;t<n;t++)//枚举未进行变换操作的行，以此行为标准 
        {
            int tmp=0;
            for(int i=0;i<n;i++)//遍历行 
            {
                int cnt=0;
                for(int j=0;j<m;j++)//遍历列 
                if(a[i][j]==a[t][j]) cnt++;
                tmp+=min(cnt,m-cnt);//注意是m-cnt了 
            }
            ans=min(ans,tmp);//记录所有方案中最小的操作次数
        }
    }

    if(ans<=k) printf("%d\n",ans);
    else puts("-1");
}

附图

解释一下解题思路中的第二点
假设确定某一行/列为标准，其中白代表0连通块，黑代表1连通块，其他各行/列的各个与标准行/列对应的区域的颜色要么相同要么相反，即各个红***域与其上方的黑白连通块对应。这是对于解出本题，至关重要的一点，另外一个突破点就是数据规模。
图片说明

总结

难点在于得出第二点结论，和分情况讨论！
感觉看题解很容易懂，但自己做还是一点思路没有。

ref

https://blog.csdn.net/qq_36679229/article/details/89014919
https://www.cnblogs.com/kuangbin/p/3702113.html