Even Parity UVA - 11464 (枚举)

野性酷女 2021-12-15 08:51 228阅读 0赞

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

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

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

#include<cstring>
    #include<iostream>
    using namespace std;
    const int maxn=20;
    const int INF=1e9;
    
    int t, n, a[maxn][maxn], b[maxn][maxn];
    int check(int s){
        memset(b, 0, sizeof(b));
        for(int c=0;c<n;++c)
            if(s&(1<<c))b[0][c]=1;
            else if(a[0][c]==1)return INF;
        for(int r=1;r<n;++r)
        for(int c=0;c<n;++c){
            int sum=0;
            if(r-2>=0)sum+=b[r-2][c];
            if(r-1>=0&&c-1>=0)sum+=b[r-1][c-1];
            if(r-1>=0&&c+1<n)sum+=b[r-1][c+1];
            b[r][c]=sum%2;
            if(a[r][c]==1&&b[r][c]==0)return INF;
        }
        int cnt=0;
        for(int r=0;r<n;++r)
        for(int c=0;c<n;++c)
        if(a[r][c]!=b[r][c])++cnt;
        return cnt;
    }
    
    
    int main(){
        cin>>t;
        for(int kase=1;kase <=t;++kase){
            cin>>n;
            for(int r=0;r<n;++r)
                for(int c=0;c<n;++c)cin>>a[r][c];
            int ans=INF;
            for(int s=0; s<(1<<n); ++s)
                ans=min(ans, check(s));
    
            if(ans==INF)ans=-1;
            cout<<"Case "<<kase<<": "<<ans<<endl;
        }
    }

转载于:https://www.cnblogs.com/ALINGMAOMAO/p/10731014.html