Uva 11464 偶数矩阵(Even Parity)

题意

给出一个 \(n \times n\) 的 01矩阵 ，你的任务是修改尽量少的0(变为1)，使得对于矩阵中每个元素，它上下左右(如果存在)的元素和为偶数。

数据有多组输入，其中 \(n \le 15\) 。

分析

首先可以想到暴力枚举每个元素的改变状态，那么一共有 \(2 ^ {15 \times 15}\) 种状态，无法接受。

对于某一行而言，如果它的前一行已经确定，那么我们可以直接确定这一行的合法状态(如果存在)。

这样我们就可以只枚举第一行的修改状态，递推后面的状态，最后确定是否合法即可。

唯一的坑点时数组要清零，因为我们计算外部的元素时需要为0，不清零会沿用上一组数据。

时间复杂度为 \(O(2 ^ {n} \times n ^ 2)\) 。

Code

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <string>
#include <sstream>
#include <cstdlib>
#include <random>
#include <algorithm>

using namespace std;

#define closeSync ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define multiCase int T; scanf("%d", &T); while ( T -- )
#define mst(a, b) memset(a, b, sizeof(a))
#define lowbit(x) (x&(-x))
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i < y; i++)
#define per(i, x, y) for(int i = x; i >= y; i--)
#define perr(i, x, y) for (int i = x-1; i >= y; i--)
#define forr(x, s) for (auto x : s)
#define all(a) begin(a),end(a)
#define gti greater<int>()
#define qgti greater<int>
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define pb emplace_back
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << endl;
typedef vector<int> veci;
typedef vector<string> vecs;
typedef pair<int, int> PII;
typedef pair<string, int> PSI;
typedef pair<char, int> PCI;
typedef long long LL;
typedef unsigned long long ULL;

const int N = 20, M = 6000, mod = 1e6 + 7, INF = 0x3f3f3f3f;
const int strHash = 13333;
const double pi = acos(-1);
const double eps = 1e-5;

/************************************* Write here ******************************************/

const int dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 };

int g[N][N], backup[N][N];
int times;

void solve ()
{
    mst(g, 0); // 记得清零，因为我们计算矩阵外元素时默认为0，不清零会沿用上一次的矩阵
    int n; scanf("%d", &n);
    rep(i, 1, n) rep(j, 1, n) scanf("%d", &g[i][j]);
    memcpy(backup, g, sizeof g); // 每次会修改数组，要备份起来

    int ans = INF;
    // 枚举第一行的所有可能状态
    repp(s, 0, (1 << n))
    {
        memcpy(g, backup, sizeof backup); // 备份数组赋值，恢复原来的数组
        bool is_success = true;
        int chg = 0; // 改变数量
        // 改变第一行
        rep(i, 1, n)
            if ((s >> i - 1) & 1)
            {
                if (g[1][i]) is_success = false;
                g[1][i] = 1, chg ++ ;
            }
        if (!is_success) continue;
        rep(i, 1, n - 1) rep(j, 1, n)
        {
            int sum = 0;
            rep(k, 0, 3) sum += g[i + dr[k]][j + dc[k]];
            if (sum & 1)
            {
                if (g[i + 1][j]) is_success = false;
                g[i + 1][j] = 1, chg ++ ;
            }
        }
        // 检查最后一行格子是否合法
        rep(i, 1, n)
        {
            int sum = 0;
            rep(k, 0, 3) sum += g[n + dr[k]][i + dc[k]];
            if (sum & 1) is_success = false;
        }
        if (is_success) ans = min(ans, chg);
    }
    printf("Case %d: %d\n", ++times, ans == INF ? -1 : ans);
}

/************************************* Write upon ******************************************/

/* Storms make trees take deeper roots.*/
signed main () 
{
    
    // init();
    multiCase
        solve();

    return 0;
}