codeforces 425B Sereja and Table（状态压缩，也可以数组模拟）

给出一个n*m的01矩阵, 让你最多改变k个里面的值(0变1,1变0)，使得0、1的连通分量是矩阵。输出最少步数

1 ≤ n, m ≤ 100; 1 ≤ k ≤ 10

题解：

如果01连通分量是矩形，

那么矩形一定是这样的：

0101010

1010101

0101010

1010101

(上面的01代表子矩阵块)。

也就是每一行要么是相同，要么是相反的。

如果n>k, 肯定有一行是不能改变的，那么枚举这一行，然后其余的要么变相同，要么变相反，看最少的步数。

如果n<k ,那么可以枚举第一列的状态(2^k), 然后其余列变成和第一列相同或者相反。

以上引用自：http://www.cnblogs.com/kuangbin/p/3702113.html

//我不知道我这种模拟算不算是状态压缩

#include <cstdio>

#include<iostream>

#include <cstring>

#include <algorithm>

#include<vector>

using namespace std;

int k,n,m;

int a[][];

int min(int x,int y)

{

    if(x<y)return x;

    return y;

}

int meijuh()

{

    int minn=;

    for(int i=;i<k+;i++)

    {

        int ans=;

        for(int ii=;ii<n;ii++)

        {

            if(i!=ii)

            {

                int sa=,di=;

                for(int j=;j<m;j++)

                {

                    if(a[i][j]==a[ii][j])

                        sa++;

                    else

                        di++;

                }

                ans+=min(sa,di);

            }

        }

        minn=min(minn,ans);

    }

    return minn;

}

int meijul()

{

    int er[][];

    for(int i=;i<;i++)er[i][]=i&;

    for(int i=;i<;i++)for(int j=;j<;j++)er[i*+j][]=i&;

    for(int i=;i<;i++)for(int j=;j<;j++)er[i*+j][]=i&;

    for(int i=;i<;i++)for(int j=;j<;j++)er[i*+j][]=i&;

    for(int i=;i<;i++)for(int j=;j<;j++)er[i*+j][]=i&;

    for(int i=;i<;i++)for(int j=;j<;j++)er[i*+j][]=i&;

    for(int i=;i<;i++)for(int j=;j<;j++)er[i*+j][]=i&;

    for(int i=;i<;i++)for(int j=;j<;j++)er[i*+j][]=i&;

    for(int i=;i<;i++)for(int j=;j<;j++)er[i*+j][]=i&;

    for(int i=;i<;i++)for(int j=;j<;j++)er[i*+j][]=i&;

    for(int i=;i<;i++)for(int j=;j<;j++)er[i*+j][]=i&;

    int minn=;

    for(int i=;i<(<<n);i++)

    {

        int ans=;

        for(int j=;j<m;j++)

        {

            int sa=,di=;

            for(int ii=;ii<n;ii++)

            {

                if(er[i][ii]==a[ii][j])

                    sa++;

                else di++;

            }

            ans=ans+min(sa,di);

        }

        minn=min(minn,ans);

    }

    return minn;

}

int main() {

    cin >>n>>m>>k;

    for(int i=;i<n;i++)

        for(int j=;j<m;j++)

            cin >>a[i][j];

    int minn=;

    if(n>k)

    {

        minn = meijuh();

    }

    else

    {

        minn=meijul();

    }

    if(minn<=k)

        cout << minn<<endl;

    else

        cout <<-<<endl;

    return ;

}