Java 中将二进制矩阵转换为零矩阵的最小翻转次数

这是一个非常有趣的问题，经常在 **Google、Amazon、TCS、Accenture** 等顶级 IT 公司的面试中出现。通过解决这个问题，可以考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将使用不同的方法和逻辑来解决 **Java 中将二进制矩阵转换为零矩阵的最小翻转次数问题**。我们还将为此创建 Java 程序。

二进制矩阵

布尔矩阵是指所有元素都为 1 或 0 的矩阵。

零矩阵

零矩阵是指所有元素都为零的矩阵。因此，元素全为零的矩阵称为 **零矩阵** 或 **空矩阵**。请注意，零矩阵可以是方阵。它用字母 **O** 表示。例如，考虑以下矩阵

问题陈述

给定一个 m*n 的二进制矩阵。一次，我们可以选择一个单元格并翻转该单元格及其所有四个邻居（如果存在）（翻转是将 1 变为 0，0 变为 1）。如果两个单元格共享一条边，则它们是邻居。

任务是返回将二进制矩阵转换为零矩阵所需的最小翻转次数，否则返回 -1。

如上所示，上述矩阵可以通过三次翻转转换为零矩阵，即 (1, 0)、(0, 1) 和最后 (1, 1)。

让我们看一些其他例子。

示例 1

输入： matrix = [[1,0,0], [1,0,0]]

输出 -1

解释： 给定的矩阵无法转换为零矩阵。

示例 2

输入： matrix = [[1,1,1], [1,0,1], [0,0,0]]

输出 6

解释： 给定的矩阵需要六次翻转才能转换为零矩阵。

问题解决方案

可以使用以下两种方法解决该问题

1. DFS、回溯和记忆化
2. BFS、记忆化和位运算

使用 DFS、回溯和记忆化

在此方法中，对于每个单元格，我们要么完全翻转它，要么翻转它一次。请注意，任何单元格都不能翻转两次。这保证了 2^(m*n) 种可能的状态，其中 m 和 n 最多为 3。因此，我们可以检查从初始状态可达的每种可能状态。它给出了从初始状态到最终状态（0）的最小转换成本。

让我们通过一个例子来理解。

考虑一个数组 say **arr**。它避免了多次出现相同状态。假设 arr[i] 是从状态 i 转换到 0 所需的最小翻转次数。

如果之前已经发生过翻转（从 i1 到 i2），这意味着我们刚刚进入了一个循环。在这个循环中，一些翻转可能是浪费的，也可能没有实现状态转换。为了克服这个问题，我们需要一个布尔数组来跟踪状态，以查看我们是否之前访问过该状态。如果我们之前访问过该状态，则返回 -1，表示翻转属于一个循环，并且不会产生可能的结果。

算法

1. 初始化 dp 和 seen 数组，dp[0] = 0；
2. 从初始状态开始，尝试翻转每个不同的单元格。然后递归地求解（步骤 i、ii 和 iii）所有给出最小成本的下一个状态。
   1. 如果我们之前访问过该状态，则返回 **-1**。这表明之前的翻转选择不会是答案；
   2. 否则，计算一个具有有效结果的状态。返回结果而不重新计算状态。
   3. 否则，我们需要使用回溯来计算状态。将状态标记为已访问。之后，对于每个可能的下一个状态，执行一次导致该下一个状态的翻转。
   4. 递归地求解这个下一个状态，然后将相同的单元格翻转回来以完成回溯。在求解完所有可能的下一个状态并更新当前状态的结果后，将当前状态标记为未访问以完成回溯。

让我们在 Java 程序中实现上述算法。

NumberOfFlip.java

输出

The minimum number of flips required is: 6

复杂度

时间复杂度和空间复杂度为 **O(2^{(m * n)})**，因为我们一次检查每个状态。

BFS、记忆化和位运算

也可以使用 **BFS** 解决该问题。在此方法中，我们将状态 S1 到 S2 的翻转（如上一种方法所示）视为一步，并跟踪每个状态的结果。当我们第一次更新某个状态的结果时，BFS 确保了从初始状态开始的最小成本。在这种情况下，我们将新状态添加到 BFS 队列中。稍后，如果我们获得相同状态的更大成本，则忽略它。该方法确保每个可能的状态只计算一次。

算法

1. 要获得初始状态，请使用位运算。
2. 最初，所有状态都设置为 Integer.MAX_VALUE，状态成本为 0。
3. 将初始状态添加到队列并执行如下 BFS：
   1. 如果到达的状态是 0，则返回其最小成本；
   2. 否则，使用 XOR 操作尝试通过在不同单元格上进行所有可能的翻转。
   3. 如果新状态是第一次计算，则将其添加到队列中。
4. 如果所有状态都用尽但未成功，则返回 -1。

让我们通过一个例子来理解。

最少步数 => BFS

关键： 将矩阵压缩为一个整数/位集。

注意：翻转整数 i 的第 i 位，即 x^=(1 << i)。

让我们将步骤实现为一个算法。

算法

让我们在 Java 程序中实现上述步骤。

Java 程序将二进制矩阵转换为零矩阵

NumberOfFlips.java

输出

The minimum number of flips required is: 3

复杂度

时间复杂度和空间复杂度为 **O(2^{(m * n)})**。请注意，此方法比前一种方法更快。