algorithm - 使用最小行和列切换将 NxN 二进制矩阵转换为零矩阵

Question

这是关于我发布的关于将一个 NxN 二进制矩阵转换为另一个 .我问的问题是代码挑战问题。但是，在 How to do matrix conversions by row and columns toggles? 上提出了类似的问题。 .我经历了那个线程，并且对如何解决问题有了一些想法。我在这里重申这个问题。

“我想编写代码来解决以下问题。我打算使用 C、C++、Java 或 Python，具体取决于哪个更方便。给定两个 NxN (1 <= N <= 2000) 个二进制矩阵(每个元素为 1 或 0 的矩阵)A 和 B。问题是使用最少的允许操作数将 A 转换为 B .允许的操作是:
1. 我们可以切换一行，
这将切换该行中的所有值，即将该行中的 1 更改为 0，将 0 更改为 1
2. 我们可以切换一列，
这将切换该列中的所有值，即将该列中的 1 更改为 0，将 0 更改为 1。
如果没有解决方案，我们打印 -1"

但是，我有以下疑问。

我知道找到将 A 转换为 B 所需的最少切换次数的第一步是计算 A XOR B 。结果中的 1 是必须切换的位置，换句话说，A XOR B 必须使用最少数量的行和列切换转换为零矩阵。但是，我不清楚如何使用最少数量的行和列切换将 A XOR B 转换为零矩阵。有人可以解释一下吗？

谢谢。

Answer 1

相当简单的任务。

首先，我们应该明白多次切换行或列是没有意义的。为了更好地理解，我们这样表示状态:每个单元格中都有 0 或 1，并且始终取模 2 的总和结果:

final[i,j] = initial[i,j] + row_switched[i] + column_switched[j]  (mod 2)

其中 row_switched 和 column_switched 是我们切换第 i 行和第 j 列的次数。现在很明显，它们的值应该是 0 或 1 以获得最少数量的开关。

但这实际上构成了一个方程组!我们知道初始状态(给定)，我们知道最终状态(零)，我们只需要针对 r[i] 和 c[j] 求解系统!

不幸的是，由于模数以及它不包括隐含在 r[i] 和 c[j] 上的约束(为 0 或1).

---

让我们不用模数重写这些条件:

row_switched[i] + column_switched[j] = 1  (if initial[i,j] = 1)
row_switched[i] - column_switched[j] = 0  (if initial[i,j] = 0)

为每个单元格编写此代码后，我们得到了一个超定义的 N^2 方程组。让我们用下面的方法来解决它。很明显，如果我们知道 row_switched[0] 的值，我们就会知道整个 column_switched[] 数组的值，因为它们由方程式，其中 row_switched[0] 参与其中。然后也很容易推断出每一行的值。

但是对于 row_switched[0] 我们只有两个变体:0 和 1。让我们尝试每个变体(参见下面的注释)，并为每个变体计算两个数组!然后我们应该检查所有方程是否成立，并选择满足整个系统并且开关较少的两个集合中的一个。

如果两者都不满足，那么，它是无解的。尝试解决这个问题，呵呵:

0 1
0 0

这样就完成了解决方案。我希望你只是为了尝试而做一个+1。 :)

---

关于为什么这是最少数量的开关的问题。事实上，任何有效数量的开关都应该满足上面概述的方程组(以 0 和 1 作为值的约束)。但是那个系统只有两个解，我们都在上面的算法中找到了。所以，上面的算法一定会找到最小的那个。

---

注意:在我看来，似乎，我们只能尝试一组。如果一个通过了系统，另一个也应该通过。一组是另一组的否定，所以我们只选择开关数较少的一组。开关总和为2N。但这只是似乎，并且不如其他部分清楚。