解决此问题的一种可能方法是将此问题视为线性方程组，只使用0和1而不是实数。

数字0和1
在XOR和AND运算下形成一个字段（顺便说一下，该字段称为GF（2））。也就是说，您可以通过对两个位进行XOR运算来“相加”在一起，并且可以通过对它们进行“与”运算来“相乘”两个位。事实证明，XOR和AND的行为与常规乘法和加法的许多属性匹配-
乘法和加法是可交换和关联的，例如，乘法分布在加法上。事实证明，这些性质足以让您使用高斯消去法来求解0s和1s上的线性方程组。例如，高斯消去法可用于求解此线性方程组：

x XOR z = 1
x XOR y XOR z = 0
y XOR z = 0

因此，如果我们可以使用XOR和AND将您的问题表达为线性方程组，那么您只需在该字段上使用标准高斯消元就可以在多项式时间内解决问题。

为此，首先要注意的是，将一位取反等于对它进行异或：

• 0 XOR 1 = 1
• 1 XOR 1 = 0

这意味着，如果您切换整个行和列，则等效于对该行和列中的所有值进行1异或。

现在，假设您有一个0×1的m×n矩阵。我们将用A [i]
[j]表示第i行和第j列中数字的值。由于切换（i，j）会切换同一行和同一列中的所有元素，因此您可以想象到切换（i，j）等效于将原始矩阵A异或为新的矩阵A，如下所示：

0 0 ... 0 1 0 ... 0
0 0 ... 0 1 0 ... 0
        ...
0 0 ... 0 1 0 ... 0
1 1 ... 1 1 1 ... 1
0 0 ... 0 1 0 ... 0
        ...
0 0 ... 0 1 0 ... 0
0 0 ... 0 1 0 ... 0

在这里，i在第i行和j列中，而0在其他地方。

注意，网格中的每个位置都会产生这些“触发矩阵”之一，从而执行操作“ flip（i，j）”的效果是对具有触发矩阵号（i，j）的当前矩阵进行XOR运算。

现在再作一次关键观察：没有最佳解决方案（操作次数最少的解决方案）会将同一位置翻转两次。这样做的原因是XOR本身会反转：XOR a
=0。因此，可以通过移除两次翻转来缩短重复两次的操作，从而缩短两次翻转相同位置的解决方案。此外，由于XOR是关联和可交换的（（x
XOR y）XOR z = x XOR（y XOR z），x XOR y = y XOR
x），因此执行最佳翻转的顺序无关紧要解。您所要做的就是，一旦知道要执行的翻转，就可以按照任意顺序执行翻转。

将所有这些结合在一起，我们试图针对每个可能的翻转确定是否应该执行该翻转。订购和数量无关紧要。

这是我们到达实际线性方程组的地方。我们给了一个起始矩阵A和一堆不同的“触发矩阵”，每个我们可以做的不同的触发。让我们用T
[i，j]表示位置（i，j）的切换矩阵。然后，我们将引入新变量b [i，j]为0或1值，指示我们是否应该实际翻转位置（i，j）。有了这种设置，我们正在寻找b
[i，j]的一组值，使得

A XOR b [1，1] T [1，1] XOR b [1，2] T [1，2] XOR … XOR b [m，n] T [m，n] = 0

其中0是零矩阵。如果有可能找到一个可行的b选项，那么您有解决方案。如果不是，则不存在解决方案。现在的问题是如何找到它们。

为此，我们将对上述系统做一个小的更改。让这个方程的两边都用A进行XOR。由于A XOR A = 0，所以从左侧抵消了A。由于A XOR 0 =
A，因此A移至右侧。现在我们有

b [1，1] T [1，1] XOR b [1，2] T [1，2] XOR … XOR b [m，n] T [m，n] = A

最后，我们将再进行一次更改。与其将A和T
[i，j]表示为矩阵，不如将它们表示为按行优先的列向量。这意味着上述方程式的线性系统实际上可以不视为矩阵的总和，而是列向量的总和。

为了达成协议，让我们定义一个矩阵T，其中T的第一列为T [1，1]，T的第二列为T [1，2]，…，T的第mn列是T [m，n]。然后，让b =（b
[1，1]，b [1，2]，…，b [m，n]）^ T（顺便说一下，这是一个转置）。在这种情况下，我们可以将上面的系统重写为

Tb = A

这很漂亮！现在，我们尝试求解向量b，以使T乘以b得出矩阵A。如上所述，由于XOR和AND形成的0和1构成一个字段，因此可以使用标准的高斯消去法来求解该系统。

那么这有多有效？矩阵T的大小为mn×mn。因此，对其进行高斯消除将花费时间O（m 3 n
3），该时间虽然很大，但对于相当小的网格来说仍然不是太差。我们也可以通过简单地找出触发哪些条目来构造时间为O（m 2 n
2）的网格。总体而言，这为您的问题提供了O（m 3 n 3）算法。好极了！

我 为“ Lights Out”游戏 实现了一个 求解器，该
实现与该问题极为相似，不同之处在于切换按钮仅翻转（i，j）附近的灯光，而不翻转整个行和列。它基于完全相同的方法，因此，如果您想使用代码并将其用作起点，则可能可以在短时间内编写该求解器。我试图在代码的相关部分添加注释，以使其易于阅读，因此希望它很有用。

希望这可以帮助！