matrix - 当只允许一个操作时，如何使 4x4 矩阵的所有条目为 1 或 0？

Question

我有一个 4x4 矩阵。说

0 1 1 0
0 0 1 0
0 1 1 0
0 1 1 1

我的任务是将矩阵转换为

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

或者

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

单次操作定义为选取矩阵中的任何元素，然后将其左、右、上、下元素和元素替换为与 1 的异或。

例子

0 1 1 0
0 0 1 0
0 1 1 0
0 1 1 1

对标记元素的操作会将矩阵转换为

0 1 0 0
0 1 0 1
0 1 0 0
0 1 1 1

我的目标是计算获得最终结果所需的最少操作次数。

我什至不明白这个问题属于什么类别？这是分支和界限，反向追踪还是其他什么。

Answer 1

你所描述的叫做lights out puzzle .有相关OEIS这为您提供了解决 n X n 正方形上的全 1 熄灯问题所需的最少非平凡开关翻转次数。

维基百科描述了 algorithm how to solve it 的一般草图.您可能还对 this answer 感兴趣这里是 SO，其中包括指向示例实现的链接。引用答案:

The idea is to set up a matrix representing the button presses a column vector representing the lights and then to use standard matrix simplification techniques to determine which buttons to press. It runs in polynomial time and does not require any backtracking.