UVA - 11464 Even Parity

第一行枚舉，用二進制思想，後面的n-1行都可以推出來。邊推邊驗證是否滿足要求。 保存最優解

 
#include<cstdio>  
#include<algorithm>  
#include<iostream>  
#include<cstring>  
using namespace std;  
int a[20][20];  
int b[20][20];  
int main()  
{  
    int cas,n;  
    cin>>cas;  
    for(int ca=1;ca<=cas;ca++)  
    {  
        scanf("%d",&n);  
        memset(a,0,sizeof(a));  
        memset(b,0,sizeof(b));  
        for(int i=1;i<=n;i++)  
            for(int j=1;j<=n;j++)  
                scanf("%d",&a[i][j]);  
        int top=(1<<n);  
        int ans=0x3f3f3f3f;  
        for(int f=0;f<top;f++)  
        {  
            int tmp=f;  
            int sum=0;  
            int ok=1;  
            for(int i=n;i>=1;i--)  
            {  
                b[1][i]=(tmp&1);  
                tmp>>=1;  
                if(b[1][i]-a[1][i]<0) {ok=0;break;}  
                if(b[1][i]!=a[1][i]) sum++;  
            }  
            if(!ok) continue;  
            for(int j=1;j<=n;j++)  
            {  
                b[2][j]=((b[1][j-1]+b[1][j+1])&1);  
                if(b[2][j]-a[2][j]<0) {ok=0;break;}  
                if(a[2][j]!=b[2][j]) sum++;  
            }  
            if(!ok) continue;  
            for(int i=3;i<=n;i++)  
            {  
                for(int j=1;j<=n;j++)  
                {  
                    b[i][j]=((b[i-1][j-1]+b[i-1][j+1]+b[i-2][j])&1);  
                    if(b[i][j]-a[i][j]<0) {ok=0;break;}  
                    if(a[i][j]!=b[i][j]) sum++;  
                }  
            }  
            if(!ok) continue;  
            for(int i=2;i<=n-1;i++)  
            {  
                for(int j=1;j<=n;j++)  
                {  
                    if(((b[i-1][j]+b[i+1][j]+b[i][j-1]+b[i][j+1])&1)) {ok=0;break;}  
                }  
                if(!ok) break;  
            }  
            if(!ok) continue;  
            for(int j=1;j<=n;j++)  
            {  
                if((b[n][j-1]+b[n-1][j]+b[n][j+1])&1) {ok=0;break;}  
                if(b[n][j]-a[n][j]<0) {ok=0;break;}  
            }  
            if(!ok) continue;  
//            for(int i=1;i<=n;i++){  
//                for(int j=1;j<=n;j++)  
//                    cout<<b[i][j];cout<<endl;}  
//            cout<<sum<<endl;  
            ans=min(ans,sum);  
        }  
        printf("Case %d: %d\n",ca,ans==0x3f3f3f3f?-1:ans);  
    }  
    return 0;  
}