UVA-11464

UVA-11464 - Even Parity

這陣子各種鬼混

然後就練了一下暴搜

我不懂為什麼有人程式執行時間可以達到我的一半...

傳說

每三個男人中

就有一隻魯蛇

不過我們先別管這個了...

#include<iostream>
#include<algorithm>
using namespace std;
int num(int ans[][16],int i,int j,int n){
    int re=0;
    if(i-2>=0)
        re+=ans[i-2][j];
    if(i-1>=0 && j-1>=0)
        re+=ans[i-1][j-1];
    if(i-1>=0 && j+1<n)
        re+=ans[i-1][j+1];
    return (re%2);
}
bool fill(int ans[][16],int map[][16],int n){
    for(int i=1 ; i<n ; i++)
    for(int j=0 ; j<n ; j++){
        ans[i][j]=num(ans,i,j,n);
        if(map[i][j]==1 && ans[i][j]==0)
            return false;
    }
    return true;
}
int diff(int ans[][16],int map[][16],int n){
    int re=0;
    for(int i=0 ; i<n ; i++)
    for(int j=0 ; j<n ; j++)
        if(ans[i][j]==1 && map[i][j]==0)
            re++;
    return re;
}
int guess(int ans[][16], int map[][16], int n, int s){
    int p=-1,ts;bool t1;
    while(++p<=(1<<n)){
        t1=true;
        for(int i=0 ; i<n && t1; i++){
            ans[0][i]=((p>>i)&1);
            if(map[0][i]==1 && ans[0][i]==0)
                t1=false;
        }
        if(t1 && fill(ans,map,n)){
            ts=diff(ans,map,n);
            s=min(s,ts);
        }
    }
    return s;
}

int main(){
    int T,t=0,n,s;
    int map[16][16];
    int ans[16][16];
    cin>>T;
    while(T>t++){
        cin>>n;
        for(int i=0 ; i<n ; i++)
            for(int j=0 ; j<n ; j++)
                cin>>map[i][j];
        s=guess(ans,map,n,256);
        if(s!=256)
            cout<<"Case "<<t<<": "<<s<<'\n';
        else
            cout<<"Case "<<t<<": -1\n";
    }
return 0;
}