LeetCode 1284. 转化为全零矩阵的最少反转次数
字数 2258 2025-12-07 11:59:03

LeetCode 1284. 转化为全零矩阵的最少反转次数

题目描述
给你一个 m x n 的二进制矩阵 mat，矩阵中的每个元素是 0 或 1。你可以执行一种操作：选中一个格子 (r, c)，然后反转这个格子以及所有相邻格子（上、下、左、右，如果存在）的值（0 变 1，1 变 0）。你的目标是将整个矩阵都变成 0。请你返回达成目标所需的最少操作次数。如果无法达成目标，返回 -1。

注意：

  • 对同一个格子执行两次操作等价于不执行任何操作，因为会相互抵消。
  • 题目保证 1 <= m, n <= 3，矩阵规模非常小。

示例 1
输入：mat = [[0,0],[0,1]]
输出：3
解释：一种可行方案是：

  1. 翻转 (1,0) → 影响 (0,0) 和 (1,0) → 矩阵变为 [[1,0],[1,1]]
  2. 翻转 (1,1) → 影响 (0,1) 和 (1,1) → 矩阵变为 [[1,1],[1,0]]
  3. 翻转 (0,0) → 影响 (0,0) 和 (1,0) → 矩阵变为 [[0,1],[0,0]]
  4. 实际上，示例解释给出的 3 步操作是另一种翻转顺序，但最少确实是 3 步。

解题思路
这个题目虽然矩阵规模很小（最多 3x3=9 个格子），但可能的操作组合非常多（每个格子可以选择翻转或不翻转）。核心思路是将矩阵状态压缩为一个整数（状态压缩），然后用 BFS 搜索从初始状态到全 0 状态的最短路径。

步骤详解

步骤 1：状态表示

  • 矩阵是二进制的，我们可以把矩阵的每一行拼接成一个二进制数。
  • 例如，2x2 矩阵 [[a,b],[c,d]] 可以表示为二进制数 (a b c d)，对应的整数是 a * 8 + b * 4 + c * 2 + d * 1（如果按行优先）。
  • 因为最多 9 个格子，所以状态可以用一个 9 位二进制整数表示，范围是 0 到 511 (2^9-1)。全 0 状态就是 0。

步骤 2：操作的影响

  • 对格子 (r, c) 执行翻转操作，会翻转自身和四个相邻格子（如果存在）。
  • 这等价于将状态整数与一个“掩码”（mask）进行按位异或（XOR）操作。掩码中，被翻转的位设为 1，其他位设为 0。
  • 例如，在 2x2 矩阵中，格子 (0,0) 的掩码是：翻转自身 (0,0) 和相邻的 (0,1)、(1,0)。对应二进制位为：(1,1,1,0) 即整数 14（如果按行优先排列是 [0,0]=1<<3, [0,1]=1<<2, [1,0]=1<<1，加起来 8+4+2=14）。

步骤 3：预先计算掩码

  • 遍历每个格子 (r, c)，计算它的操作掩码。
  • 对于每个格子，将自身和上下左右四个邻居（在矩阵范围内）的对应位设为 1。
  • 如何计算对应位？可以给每个格子一个编号：index = r * n + c，那么掩码中对应位就是 1 << index。

步骤 4：BFS 搜索最短路径

  • 初始状态：将矩阵转换为整数 start。
  • 目标状态：整数 0。
  • 使用队列进行 BFS，队列中存储 (状态, 步数)。
  • 从初始状态开始，尝试对每个可能的操作（即每个格子对应的掩码）进行翻转：next = state ^ mask。
  • 如果 next 没有被访问过，就加入队列，并标记已访问。
  • 如果遇到状态 0，返回当前步数。
  • 如果队列为空还没遇到 0，说明不可达，返回 -1。

步骤 5：为什么 BFS 可行？

  • 每次操作都会改变状态，且步长是 1（一次操作）。
  • 因为总共只有 512 种状态，BFS 可以在有限时间内完成。
  • 注意：BFS 时需要记录已访问状态，防止重复访问。

举例说明
以 mat = [[0,0],[0,1]] 为例：

  • 矩阵 2x2，格子编号：
    (0,0): index=0, (0,1): index=1,
    (1,0): index=2, (1,1): index=3。
  • 初始状态：二进制 0 0 0 1 即整数 1。
  • 预先计算每个格子的掩码：
    (0,0)：影响 index=0,1,2 → 掩码 = 1<<0 | 1<<1 | 1<<2 = 1+2+4=7
    (0,1)：影响 index=0,1,3 → 掩码 = 1+2+8=11
    (1,0)：影响 index=0,2,3 → 掩码 = 1+4+8=13
    (1,1)：影响 index=1,2,3 → 掩码 = 2+4+8=14
  • BFS 过程：
    初始状态 1，步数 0。
    从状态 1 出发，尝试四种操作：
    • 1 ^ 7 = 6 (步数 1)
    • 1 ^ 11 = 10 (步数 1)
    • 1 ^ 13 = 12 (步数 1)
    • 1 ^ 14 = 15 (步数 1)
      继续从这些状态出发，直到遇到状态 0。可以验证，从状态 1 到状态 0 的最短路径是 3 步。

复杂度分析

  • 状态数：最多 2^(m*n) ≤ 512。
  • 每个状态尝试 m*n 种操作（最多 9 种）。
  • 总时间复杂度 O(2^(mn) m * n)，在本题约束下是可行的。
  • 空间复杂度 O(2^(m*n)) 存储已访问状态。

总结
这道题的关键在于：

  1. 状态压缩，将矩阵转为整数。
  2. 将每个操作转化为与一个掩码的异或。
  3. 用 BFS 求最短路径，因为操作步长一致。
  4. 注意小规模下 BFS 是高效的。

通过这种方法，我们可以系统性地搜索所有可能的状态变化，找到最少翻转次数。

LeetCode 1284. 转化为全零矩阵的最少反转次数 题目描述 给你一个 m x n 的二进制矩阵 mat ，矩阵中的每个元素是 0 或 1。你可以执行一种操作：选中一个格子 (r, c) ，然后反转这个格子以及所有相邻格子（上、下、左、右，如果存在）的值（0 变 1，1 变 0）。你的目标是 将整个矩阵都变成 0 。请你返回达成目标所需的 最少操作次数 。如果无法达成目标，返回 -1。 注意： 对同一个格子执行两次操作等价于不执行任何操作，因为会相互抵消。 题目保证 1 <= m, n <= 3 ，矩阵规模非常小。 示例 1 输入：mat = [ [ 0,0],[ 0,1] ] 输出：3 解释：一种可行方案是： 翻转 (1,0) → 影响 (0,0) 和 (1,0) → 矩阵变为 [ [ 1,0],[ 1,1] ] 翻转 (1,1) → 影响 (0,1) 和 (1,1) → 矩阵变为 [ [ 1,1],[ 1,0] ] 翻转 (0,0) → 影响 (0,0) 和 (1,0) → 矩阵变为 [ [ 0,1],[ 0,0] ] 实际上，示例解释给出的 3 步操作是另一种翻转顺序，但最少确实是 3 步。 解题思路 这个题目虽然矩阵规模很小（最多 3x3=9 个格子），但可能的操作组合非常多（每个格子可以选择翻转或不翻转）。核心思路是将矩阵状态压缩为一个整数（状态压缩），然后用 BFS 搜索从初始状态到全 0 状态的最短路径。 步骤详解 步骤 1：状态表示 矩阵是二进制的，我们可以把矩阵的每一行拼接成一个二进制数。 例如，2x2 矩阵 [[a,b],[c,d]] 可以表示为二进制数 (a b c d) ，对应的整数是 a * 8 + b * 4 + c * 2 + d * 1 （如果按行优先）。 因为最多 9 个格子，所以状态可以用一个 9 位二进制整数表示，范围是 0 到 511 (2^9-1)。全 0 状态就是 0。 步骤 2：操作的影响 对格子 (r, c) 执行翻转操作，会翻转自身和四个相邻格子（如果存在）。 这等价于将状态整数与一个“掩码”（mask）进行按位异或（XOR）操作。掩码中，被翻转的位设为 1，其他位设为 0。 例如，在 2x2 矩阵中，格子 (0,0) 的掩码是：翻转自身 (0,0) 和相邻的 (0,1)、(1,0)。对应二进制位为： (1,1,1,0) 即整数 14（如果按行优先排列是 [0,0]=1<<3, [0,1]=1<<2, [1,0]=1<<1 ，加起来 8+4+2=14）。 步骤 3：预先计算掩码 遍历每个格子 (r, c)，计算它的操作掩码。 对于每个格子，将自身和上下左右四个邻居（在矩阵范围内）的对应位设为 1。 如何计算对应位？可以给每个格子一个编号： index = r * n + c ，那么掩码中对应位就是 1 << index 。 步骤 4：BFS 搜索最短路径 初始状态：将矩阵转换为整数 start 。 目标状态：整数 0。 使用队列进行 BFS，队列中存储 (状态, 步数)。 从初始状态开始，尝试对每个可能的操作（即每个格子对应的掩码）进行翻转： next = state ^ mask 。 如果 next 没有被访问过，就加入队列，并标记已访问。 如果遇到状态 0，返回当前步数。 如果队列为空还没遇到 0，说明不可达，返回 -1。 步骤 5：为什么 BFS 可行？ 每次操作都会改变状态，且步长是 1（一次操作）。 因为总共只有 512 种状态，BFS 可以在有限时间内完成。 注意：BFS 时需要记录已访问状态，防止重复访问。 举例说明 以 mat = [ [ 0,0],[ 0,1] ] 为例： 矩阵 2x2，格子编号： (0,0): index=0, (0,1): index=1, (1,0): index=2, (1,1): index=3。 初始状态：二进制 0 0 0 1 即整数 1。 预先计算每个格子的掩码： (0,0)：影响 index=0,1,2 → 掩码 = 1<<0 | 1<<1 | 1< <2 = 1+2+4=7 (0,1)：影响 index=0,1,3 → 掩码 = 1+2+8=11 (1,0)：影响 index=0,2,3 → 掩码 = 1+4+8=13 (1,1)：影响 index=1,2,3 → 掩码 = 2+4+8=14 BFS 过程： 初始状态 1，步数 0。 从状态 1 出发，尝试四种操作： 1 ^ 7 = 6 (步数 1) 1 ^ 11 = 10 (步数 1) 1 ^ 13 = 12 (步数 1) 1 ^ 14 = 15 (步数 1) 继续从这些状态出发，直到遇到状态 0。可以验证，从状态 1 到状态 0 的最短路径是 3 步。 复杂度分析 状态数：最多 2^(m* n) ≤ 512。 每个状态尝试 m* n 种操作（最多 9 种）。 总时间复杂度 O(2^(m n) m * n)，在本题约束下是可行的。 空间复杂度 O(2^(m* n)) 存储已访问状态。 总结 这道题的关键在于： 状态压缩，将矩阵转为整数。 将每个操作转化为与一个掩码的异或。 用 BFS 求最短路径，因为操作步长一致。 注意小规模下 BFS 是高效的。 通过这种方法，我们可以系统性地搜索所有可能的状态变化，找到最少翻转次数。