题解 | 小O的矩阵变换

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

static inline int read_bit() {
    char ch;
    while (cin >> ch) {
        if (ch == '0' || ch == '1') return ch - '0';
    }
    return 0; // 不会到这里
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<vector<int>> A(n, vector<int>(n));
        vector<vector<int>> B(n, vector<int>(n));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                A[i][j] = read_bit();
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                B[i][j] = read_bit();
        // D = A xor B
        vector<vector<int>> D(n, vector<int>(n));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                D[i][j] = A[i][j] ^ B[i][j];
        // 可行性检查：D[i][j] == D[i][0] ^ D[0][j] ^ D[0][0]
        bool ok = true;
        for (int i = 0; i < n && ok; ++i)
            for (int j = 0; j < n; ++j)
                if ((D[i][0] ^ D[0][j] ^ D[0][0]) != D[i][j]) {
                    ok = false;
                    break;
                }

        if (!ok) {
            cout << -1 << '\n';
            continue;
        }
        // 构造 r,c 并求最少操作
        vector<int> r(n), c(n);
        for (int i = 0; i < n; ++i) r[i] = D[i][0];
        for (int j = 0; j < n; ++j) c[j] = D[0][j] ^ D[0][0];
        int sr = accumulate(r.begin(), r.end(), 0);
        int sc = accumulate(c.begin(), c.end(), 0);
        int ans = min(sr + sc, 2 * n - (sr + sc));
        cout << ans << '\n';
    }
    return 0;
}