P4715 偶数矩阵（提高）

解题思路

给你一个 n×n 的 01 矩阵，每个元素非 0 即 1。任务是：把尽量少的 0 改成 1，使得矩阵中每个元素的上、下、左、右四个方向上的邻居（如果存在的话）的和都是偶数。注意只能把 0 改成 1，不能把 1 改成 0。如果无论如何都做不到，输出 -1。

先想清楚一个关键性质：一旦第一行确定了，后面的每一行就都被"逼"出来了。为什么？因为当我们处理到第 i 行第 j 列的格子时，第 i-1 行第 j 列那个格子的"上、左、右"三个邻居都已经确定了（上面是第 i-2 行的格子，左右是第 i-1 行的格子），要让这个格子的邻居和为偶数，第 i 行第 j 列这个格子取 0 还是取 1 是唯一确定的——它必须等于（上 + 左 + 右）除以 2 的余数。

这就像玩扫雷游戏：第一行一旦点下去，后面每一行哪里是雷就被唯一确定了，不需要再选择。

于是算法就是枚举第一行的 2^n 种状态：

1. 根据第一行的某个状态，逐行往下推，算出整个矩阵。
2. 推导过程中要检查合法性：如果某个位置原来就是 1，而方案要求它是 0，那就等于"把 1 改成 0"，是不允许的，这个方案直接作废。
3. 推完整个矩阵后，还要单独检查最后一行：因为最后一行没有"下一行"来救它，它自己的邻居和必须已经满足偶数条件。
4. 统计这个方案里"由 0 改成了 1"的格子个数，在所有合法方案中取最小值。

如果所有方案都不合法，说明无解，输出 -1。

边界情况：比如 n 很小的时候，格子可能只有两个甚至一个邻居，数组下标判断时要小心不要越界，代码里用 if 判断了 i-2、j-1、j+1 等下标是否合法。

参考代码

// 偶数矩阵：枚举第一行，逐行贪心确定，求改变0为1的最少次数
#include <iostream>
using namespace std;
int orig[16][16]; // 原始矩阵
int now[16][16];  // 当前方案
int n;
// 按第一行状态 mask 计算需要改变的数量，无解返回很大数
int solveMask(int mask) {
    int cnt = 0;
    // 第一行：若原位置是1而mask要求是0，则不能把1改0，无解
    for (int j = 0; j < n; j++) {
        int v = (mask >> j) & 1;
        if (orig[0][j] == 1 && v == 0) return 1000000;
        now[0][j] = v;
        if (v == 1 && orig[0][j] == 0) cnt++;
    }
    // 逐行确定：让上一行每个元素上、下、左、右之和为偶数
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 元素(i-1,j)的邻居中已确定的三个：上、左、右
            int sum = 0;
            if (i - 2 >= 0) sum += now[i - 2][j];
            if (j - 1 >= 0) sum += now[i - 1][j - 1];
            if (j + 1 < n) sum += now[i - 1][j + 1];
            int v = sum % 2; // 使(i-1,j)邻居和为偶数时，(i,j)应为v
            if (orig[i][j] == 1 && v == 0) return 1000000; // 不能把1改0
            now[i][j] = v;
            if (v == 1 && orig[i][j] == 0) cnt++;
        }
    }
    // 检查最后一行：只考虑上、左、右三个邻居
    for (int j = 0; j < n; j++) {
        int sum = 0;
        if (n - 2 >= 0) sum += now[n - 2][j];
        if (j - 1 >= 0) sum += now[n - 1][j - 1];
        if (j + 1 < n) sum += now[n - 1][j + 1];
        if (sum % 2 != 0) return 1000000;
    }
    return cnt;
}
int main() {
    // 可能有多组数据，一直读到文件结束
    while (cin >> n) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) cin >> orig[i][j];
        int best = 1000000;
        for (int mask = 0; mask < (1 << n); mask++) {
            int r = solveMask(mask);
            if (r < best) best = r;
        }
        if (best == 1000000) cout << -1 << endl;
        else cout << best << endl;
    }
    return 0;
}

复杂度分析

算法要枚举第一行的 2^n 种状态，每一种状态都要推导整个 n×n 矩阵，推导耗时 O(n²)。所以总时间复杂度是 O(2^n × n²)。当 n≤15 时，2^15×225≈737 万次运算，运行很快；如果 n 再大，这个算法就会明显变慢，所以这类题对 n 有一定的限制。

空间方面，需要两个 n×n 的数组分别存原始矩阵和当前方案，空间复杂度 O(n²)。