小O的矩阵变换

2026/10/24约 2033 字大约 7 分钟

小O的矩阵变换

OPPO 笔试真题 · 2024 秋招 · 研发通用岗 / 2024 秋招 · 后端开发
判题请到牛客原题提交。

题目描述

小O有两个 $n$ 行 $n$ 列的01方阵 $A$ 和 $B$ ，他希望用最少的操作次数将 $A$ 和 $B$ 变相等。具体的，每次操作他可以选择 $A$ 矩阵的一行或者一列，将此行或列的所有数字进行反转，即：0变1, 1变0。

他想知道自己最少需要几次操作可以做到，或者永远无法做到，请你帮帮他吧。

输入格式

每个测试文件均包含多个测试点。第一行输入一个整数 $T\ (1\le T\le 10)$ 代表测试数据组数，每组测试数据描述如下：

第一行输入一个 $n\ (1 \leq n \leq 4)$ ，表示方阵的长和宽。

此后 $n$ 行，每行输入 $n$ 个整数（保证为 0 或者 1），表示方阵 $A$ 。

此后 $n$ 行，每行输入 $n$ 个整数（保证为 0 或者 1），表示方阵 $B$ 。

输出格式

对于每组测试数据，在一行上输出一个整数表示最少的操作次数，如果无法将 $A$ 变为 $B$ ，输出 $-1。$

示例

示例 1

输入：

输出：

2
-1

说明：

第一个测试数据：

0 1

1 0

操作一次第一行变成：

1 0

再操作第二行变成：

1 0

0 1

因此最少需要 2 次。

解题思路

第一步：把「A 变成 B」换成「把差异消成 0」

逐格盯着 A 和 B 看没有意义，先造一个差异矩阵 $D$ ：

D[i][j] = A[i][j] \oplus B[i][j]

$D$ 里是 1 的格子，就是「被翻了奇数次才能对上」的格子。于是把 A 变成 B，
等价于把 $D$ 变成全 0。

一次操作翻一整行（或一整列），所以：

格子 $(i,j)$ 被翻的总次数 = 第 $i$ 行被翻的次数 + 第 $j$ 列被翻的次数；
同一行翻两次等于没翻，只有奇偶性有意义。

因此每个开关（每一行、每一列）都只需要考虑「翻 0 次」还是「翻 1 次」，
方案可以由 $2n$ 个 0/1 变量描述：

D[i][j] \text{ 清零} \iff row[i] \oplus col[j] = D[i][j]

第二步：为什么可以直接枚举

$n \le 4$ ，于是 $2n \le 8$ ，全部开关组合只有

2^{2n} \le 2^8 = 256

种。每组数据把这 256 种都试一遍，每种逐格校验 $n^2 \le 16$ 次，单组最多
4000 多次比较； $T \le 10$ ，总共几万次运算。

这里的暴力不是「退而求其次」——状态空间本来就小到不需要更聪明的做法，
枚举反而是最不容易写错的解法。

第三步：用二进制掩码枚举，用 popcount 数操作次数

把 $2n$ 个开关压进一个整数 mask：低 n 位表示哪些行翻，高 n 位表示哪些
列翻。那么

第 $i$ 行是否翻：(mask >> i) & 1
第 $j$ 列是否翻：(mask >> (n + j)) & 1
这个方案的操作次数：bin(mask).count("1")

对每个 mask，逐格验证

A[i][j] ^ 行开关 ^ 列开关 == B[i][j]

全部格子都通过就是一个合法方案，更新最小操作数；所有 mask 都不合法就输出
-1。

完整代码实现

import sys


def min_ops(a, b, n):
    """枚举 2n 个开关的全部子集，返回最少操作次数；无解返回 -1"""
    best = -1
    for mask in range(1 << (2 * n)):
        ok = True
        for i in range(n):
            flip_row = (mask >> i) & 1           # 第 i 行是否翻转
            for j in range(n):
                flip_col = (mask >> (n + j)) & 1  # 第 j 列是否翻转
                if (a[i][j] ^ flip_row ^ flip_col) != b[i][j]:
                    ok = False
                    break
            if not ok:
                break
        if not ok:
            continue
        ops = bin(mask).count("1")               # 这个子集里翻了几条线
        if best == -1 or ops < best:
            best = ops
    return best


def solve() -> None:
    """按测试组读入两个方阵，逐组枚举求最少操作次数"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    pos = 0
    t = int(data[pos]); pos += 1
    out = []
    for _ in range(t):
        n = int(data[pos]); pos += 1
        a = []
        for _ in range(n):
            a.append([int(x) for x in data[pos:pos + n]])
            pos += n
        b = []
        for _ in range(n):
            b.append([int(x) for x in data[pos:pos + n]])
            pos += n
        out.append(str(min_ops(a, b, n)))
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

示例推演

第一组数据：n = 2

A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix},\quad B = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix},\quad D = A \oplus B = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}

$D$ 全是 1，需要每格都被翻奇数次。逐个试开关：

方案	每一格翻的次数	结果
只翻第 1 行	该行 1 次、另一行 0 次	第一行变 0、第二行仍是 1，不对
只翻第 1 列	该列 1 次、另一列 0 次	同理不对
翻第 1、2 两行	每格 1 次	全变 0，操作 2 次
翻第 1、2 两列	每格 1 次	全变 0，操作 2 次

最少 2 次。题面说明里的「翻第一行再翻第二行」正是上表第三种方案。

第二组数据：n = 2

A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix},\quad B = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix},\quad D = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}

设四个开关为 $r_1, r_2, c_1, c_2$ ，逐格列出方程：

格子	$D$	方程
(1,1)	0	$r_1 \oplus c_1 = 0 \Rightarrow r_1 = c_1$
(1,2)	1	$r_1 \oplus c_2 = 1$
(2,1)	1	$r_2 \oplus c_1 = 1 \Rightarrow r_2 = 1 \oplus r_1$
(2,2)	1	$r_2 \oplus c_2 = 1$

把第三式代入第四式： $(1 \oplus r_1) \oplus c_2 = 1 \Rightarrow r_1 \oplus c_2 = 0$ ，
与第二式的 $r_1 \oplus c_2 = 1$ 矛盾。所以无论怎么翻都做不到，输出 -1。

复杂度分析

解法	时间复杂度	空间复杂度	说明
枚举全部开关子集（本文）	$O(T \cdot 2^{2n} \cdot n^2)$	$O(n^2)$	$n \le 4$ ，单组最多 256 种方案 × 16 格
只枚举第一行/第一列	$O(T \cdot 2^{n} \cdot n^2)$	$O(n^2)$	其余开关由第一行推出，详见扩展思考

两个做法在本题规模下都是毫秒级，选更容易写对的枚举。

易错点总结

1. 以为可以只翻一个格子

操作的最小单位是整行或整列。所以「 $2 \times 2$ 矩阵只差一个角」这种情形是
无解，不要输出 1。

2. 把「翻两次」也当成方案

同一行翻两次等于没翻，只有奇偶性起作用。枚举的应该是 0/1 子集，而不是
「每行翻几次」；否则搜索空间无穷大，而且会重复计算等价的方案。

3. 掩码的位分配写错

低 $n$ 位给行、高 $n$ 位给列。取位时是 mask >> i 与 mask >> (n + j)，
两者不能写反。在方阵上写反得到的差异往往仍然「看起来合理」，样例也可能
蒙对。

4. 多组数据没有推进读取位置

输入把所有数据摊成一串 token：T、n、 $n^2$ 个 A、 $n^2$ 个 B、n、……
必须用一个游标顺序取，每读一段就推进，否则第二组开始就串位。

5. 最小值的初值

用 -1 表示「还没找到」，或者用 2n + 1 当无穷大。初值写 0 会让答案
永远是 0。

扩展思考

只要确定第一行怎么翻，其余的开关就被钉死了。由
$D[i][j] = row[i] \oplus col[j]$ ，固定 $col[0]$ 之后
$row[i] = D[i][0] \oplus col[0]$ ，再由第一行解出所有 $col[j]$ 。
所以只需枚举 $2^n$ 种（第一行的翻法或第一列的翻法），再花 $O(n^2)$ 校验，
复杂度可以降到 $O(T \cdot 2^n n^2)$ 。
这个问题本质是 GF(2) 上的线性方程组：未知量 $2n$ 个、方程 $n^2$ 个。
本题的枚举就是它最朴素的解法； $n$ 再大才需要真的做高斯消元。
如果把操作换成「翻任意一个子矩阵」，结构会完全不同（变成二维差分 +
前缀和的问题）。