小O的矩阵变换

[题目链接](https://www.nowcoder.com/practice/b1c40c55c4724f75a659915c6700e5ce)

思路

给定两个 $n \times n$ 的 01 矩阵 $A$ 和 $B$ ，每次操作可以选择 $A$ 的某一行或某一列，将该行/列所有元素翻转（0 变 1，1 变 0）。求最少操作次数使 $A$ 变为 $B$ ，若不可能输出 -1。

建模

设 $r_i \in \{0, 1\}$ 表示第 $i$ 行是否被翻转， $c_j \in \{0, 1\}$ 表示第 $j$ 列是否被翻转（翻转偶数次等价于不翻转，所以每行/列只需考虑翻转 0 或 1 次）。

对于每个位置 $(i, j)$ ，翻转后的值为 $A[i][j] \oplus r_i \oplus c_j$ ，要求等于 $B[i][j]$ ，即：

$ $r_i \oplus c_j = A[i][j] \oplus B[i][j]$ $

令 $D[i][j] = A[i][j] \oplus B[i][j]$ ，问题变为：能否找到 $r_i, c_j \in \{0,1\}$ ，使得对所有 $(i, j)$ 满足 $r_i \oplus c_j = D[i][j]$ 。

枚举固定 $r_0$

整个方程组由 $n + n$ 个未知数（ $r_0, \ldots, r_{n-1}$ 和 $c_0, \ldots, c_{n-1}$ ）组成。只要确定 $r_0$ 的值（0 或 1），其余变量均可唯一确定：

由第 0 行约束： $c_j = D[0][j] \oplus r_0$ ，确定所有 $c_j$ ；
由第 $i$ 列第 0 列约束： $r_i = D[i][0] \oplus c_0$ ，确定所有 $r_i$ 。

确定所有变量后，遍历全矩阵验证 $r_i \oplus c_j = D[i][j]$ 是否对所有位置成立。若成立，操作次数为 $\sum r_i + \sum c_j$ 。

对 $r_0 = 0$ 和 $r_0 = 1$ 分别尝试，取两者中满足条件的最小操作数；若两者均不满足，输出 -1。

样例演示

第一组（ $n=2$ ）：

$ $D = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ $

取 $r_0 = 1$ ： $c_0 = D[0][0] \oplus 1 = 0$ ， $c_1 = D[0][1] \oplus 1 = 0$ ， $r_1 = D[1][0] \oplus c_0 = 1$ 。

验证： $r_0 \oplus c_1 = 1 = D[0][1]$ ， $r_1 \oplus c_0 = 1 = D[1][0]$ ， $r_1 \oplus c_1 = 1 = D[1][1]$ ，全部通过。

操作次数 $= r_0 + r_1 + c_0 + c_1 = 1 + 1 + 0 + 0 = 2$ 。

取 $r_0 = 0$ 同理得操作次数也为 2。答案为 2。

复杂度

时间复杂度： $O(T \cdot n^2)$ ，每组数据枚举两个 $r_0$ 值，每次 $O(n^2)$ 验证。
空间复杂度： $O(n^2)$ 。

代码

[sol-C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<vector<int>> A(n, vector<int>(n)), B(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> A[i][j];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> B[i][j];

        vector<int> r(n), c(n);
        int ans = INT_MAX;

        for (int r0 = 0; r0 <= 1; r0++) {
            r[0] = r0;
            for (int j = 0; j < n; j++)
                c[j] = (A[0][j] ^ B[0][j]) ^ r[0];
            for (int i = 1; i < n; i++)
                r[i] = (A[i][0] ^ B[i][0]) ^ c[0];

            bool ok = true;
            for (int i = 0; i < n && ok; i++)
                for (int j = 0; j < n && ok; j++)
                    if ((r[i] ^ c[j]) != (A[i][j] ^ B[i][j]))
                        ok = false;

            if (ok) {
                int ops = 0;
                for (int i = 0; i < n; i++) ops += r[i];
                for (int j = 0; j < n; j++) ops += c[j];
                ans = min(ans, ops);
            }
        }

        cout << (ans == INT_MAX ? -1 : ans) << "\n";
    }

    return 0;
}

[sol-Java]

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            int[][] A = new int[n][n];
            int[][] B = new int[n][n];

            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++)
                    A[i][j] = Integer.parseInt(st.nextToken());
            }
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++)
                    B[i][j] = Integer.parseInt(st.nextToken());
            }

            int[] r = new int[n];
            int[] c = new int[n];
            int ans = Integer.MAX_VALUE;

            for (int r0 = 0; r0 <= 1; r0++) {
                r[0] = r0;
                for (int j = 0; j < n; j++)
                    c[j] = (A[0][j] ^ B[0][j]) ^ r[0];
                for (int i = 1; i < n; i++)
                    r[i] = (A[i][0] ^ B[i][0]) ^ c[0];

                boolean ok = true;
                outer:
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++)
                        if ((r[i] ^ c[j]) != (A[i][j] ^ B[i][j])) {
                            ok = false;
                            break outer;
                        }

                if (ok) {
                    int ops = 0;
                    for (int i = 0; i < n; i++) ops += r[i];
                    for (int j = 0; j < n; j++) ops += c[j];
                    ans = Math.min(ans, ops);
                }
            }

            sb.append(ans == Integer.MAX_VALUE ? -1 : ans).append('\n');
        }

        System.out.print(sb);
    }
}