OPPO · 穷举 · 算法编程题
OPPO 穷举 n ≤ 4 时限 1 秒 / 256 MB

题目描述

小O有两个 n 行 n 列的01方阵 A 和 B ，他希望用最少的操作次数将 A 和 B 变相等。具体的，每次操作他可以选择 A 矩阵的一行或者一列，将此行或列的所有数字进行反转，即：0变1, 1变0。
他想知道自己最少需要几次操作可以做到，或者永远无法做到，请你帮帮他吧。

输入输出

输入描述
每个测试文件均包含多个测试点。第一行输入一个整数 T(1≤ T≤ 10) 代表测试数据组数，每组测试数据描述如下：
第一行输入一个 n(1 ≤ n ≤ 4) ，表示方阵的长和宽。
此后 n 行，每行输入 n 个整数（保证为 0 或者 1），表示方阵 A 。
此后 n 行，每行输入 n 个整数（保证为 0 或者 1），表示方阵 B 。
输出描述
对于每组测试数据，在一行上输出一个整数表示最少的操作次数，如果无法将 A 变为 B ，输出 -1。

样例共 1 组

样例 1 · 第一个测试数据： 0 1 1 0 操作一次第一行变成： 1 0 1 0 再操作第二行变成： 1 0 0 1 因此最少需要 2 次。
输入
2
2
0 1
1 0
1 0
0 1
2
0 1
1 1
0 0
0 0
输出
2
-1

算法解析依据充分

考点：穷举

数据规模 n ≤ 4 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：T ≤ 10，n ≤ 4
  • 复杂度门槛：允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：穷举

把候选答案空间全部列出来逐一检验，靠数据范围小来兜底。

思路框架（穷举 通法 · 非本题专属）

  1. 确定枚举什么（下标区间 / 子集 / 数值）。
  2. 用一层或多层循环（或递归）生成所有候选。
  3. 对每个候选判断是否满足题目条件，满足就统计或更新最优值。
  4. 先按数据范围估算枚举量，确认不会超时。

实现要点：多重循环是最直接的写法；枚举组合时可用递归 + 回溯，或用位掩码代表子集。

复杂度：时间 O(候选数 × 单次校验代价) ｜ 空间 O(1)

该范式的通法易错点

  • 没先估复杂度，枚举量超出时限（这是最常见的超时原因）。
  • 去重没做好，同一种方案被多次统计。

对照本题

  • 数据规模 n ≤ 4，允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。

样例解读

样例 1：输入 2 / 2 / 0 1 / 1 0 / 1 0 / 0 1 / 2 / 0 1 / 1 1 / 0 0 / 0 0 → 输出 2 / -1

第一个测试数据：

0 1

1 0

操作一次第一行变成：

1 0

1 0

再操作第二行变成：

1 0

0 1

因此最少需要 2 次。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2024年秋招-OPPO-后端开发笔试；2024年秋招-OPPO-研发通用岗笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解