题解 UVA11464 Even Parity

题意：

给你一个矩阵，求最小的操作次数（将变为）使得矩阵满足条件（节点的上下左右四个方向总和为偶数）

思路：

每个合法的矩阵都可以通过第一行推出来，

所以我们可以通过枚举矩阵的第一行，然后判断是否能成为合法的矩阵，

但是必须要满足条件（不能讲原矩阵中的改为）

因为很小，所以这种枚举是能过的

实现：

我们考虑要确定当前这个点的状态了，

我们要保证这个点满足条件，

所以tmp[i][j]=(tmp[i-2][j]+tmp[i-1][j-1]+tmp[i-1][j+1])&1

然后判断一下是否合法就好了

代码：

#include<bits/stdc++.h>

namespace Tethys{
    inline long long read(){
        long long s = 0, f = 1; char ch;
        while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
        for(s = ch ^ 48; isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
        return (s *= f);
    }
}

using namespace std;
using namespace Tethys;
const int N = 15 + 5, INF = 666;

int T, n, ans;
int a[N][N], tmp[N][N];

int dfs(int now){
    int res = 0;
    for(int i = 0; i <= n; i ++){
        for(int j = 0; j <= n + 1; j ++) tmp[i][j] = 0;
    }
    for(int i = 1; i <= n; i ++){
        if(now & (1 << (i - 1))) tmp[1][i] = 1;
        if(!tmp[1][i] && a[1][i]) return INF;
        if(tmp[1][i] && !a[1][i]) res ++;
    }
    for(int i = 2; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            tmp[i][j] = (tmp[i - 2][j] + tmp[i - 1][j - 1] + tmp[i - 1][j + 1]) & 1;
            if(!tmp[i][j] && a[i][j]) return INF;
            if(tmp[i][j] && !a[i][j]) res ++;
        }
    }
    return res;
}

signed main(){

    T = read();
    for(int t = 1; t <= T; t ++){
        n = read(); ans = INF;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= n; j ++) a[i][j] = read();
        }
        for(int i = 0; i < (1 << n); i ++) ans = min(ans, dfs(i));

        printf("Case %d: %d\n", t, ans == INF ? -1 : ans);
    }

    fclose(stdin); fclose(stdout);
    return 0;
}

完美撒花✿✿ヽ(°▽°)ノ✿