Even Parity UVA - 11464 (枚举)

时间：2022-05-23 08:59:06

从来没有觉得枚举有多费脑子的。但是这道题还是很香的。

思路：就是非常简单的枚举啦。   从一般的枚举开始考虑。一般的做法就是在所有的格子中有两种状态1， 0. 而一共有225个格子，所有一共要枚举的情况就是2255我们大概粗略的计算一下10大约是23则，时间复杂度大概是1085而实际的情况比这个要高。肯定不行。

　　　但是，通过打草稿发现，只要第一行确定了第二行一定是唯一的，同理第三行也是唯一的。这样的话直接枚举第一行就行了呀！

#include<cstring>

#include<iostream>

using namespace std;

const int maxn=;

const int INF=1e9;

int t, n, a[maxn][maxn], b[maxn][maxn];

int check(int s){

    memset(b, , sizeof(b));

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

        if(s&(<<c))b[][c]=;

        else if(a[][c]==)return INF;

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

    for(int c=;c<n;++c){

        int sum=;

        if(r->=)sum+=b[r-][c];

        if(r->=&&c->=)sum+=b[r-][c-];

        if(r->=&&c+<n)sum+=b[r-][c+];

        b[r][c]=sum%;

        if(a[r][c]==&&b[r][c]==)return INF;

    }

    int cnt=;

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

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

    if(a[r][c]!=b[r][c])++cnt;

    return cnt;

}

int main(){

    cin>>t;

    for(int kase=;kase <=t;++kase){

        cin>>n;

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

            for(int c=;c<n;++c)cin>>a[r][c];

        int ans=INF;

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

            ans=min(ans, check(s));

        if(ans==INF)ans=-;

        cout<<"Case "<<kase<<": "<<ans<<endl;

    }

}

相关文章