algorithm - 大网格上的熄灯拼图

Question

我正在尝试解决 this算法问题。为方便起见，我将其复制如下:

We are given a grid G of size N x M (1 <= N,M <= 1000) containing only 1s and 0s. If we choose one of the cells, this will toggle the value in adjacent cells (and that cell itself). Two cells that differ by exactly 1 row or 1 column are considered adjacent (i.e. diagonal cells are not adjacent). Our goal is to find a grid G' containing 1s at cell positions that we need to choose in order to turn all cells in G to 0 (those cells that we don't have to choose are marked with 0). Given any G (in this problem), G' is guaranteed to exist.

Note: There is no wraparound in the grid.

例如，如果 G 给出如下:

000
100
000

如果我们选择中心单元格，G 将变为:

010
011
010

对于这个例子，G'是:

001
011
001

它看起来与 lights-out puzzle 非常相似.我只能使用蛮力解决小实例(N，M <= 20)的问题。在谷歌上搜索也产生了一个使用高斯消去法的解决方案(用于熄灯谜题)。但这仅适用于小网格 (N,M <= 100)，因为此方法具有立方时间复杂度。

有人可以告诉我如何解决这个问题吗？

Answer 1

高斯消元没有立方时间复杂度。 NxN 矩阵需要 O(N^3) 时间，但就输入大小而言，这只是 O(N^1.5)

在 NxM 网格上使用高斯消元法解决熄灯难题需要 O(N^2*M) 时间和 O(N*M) 空间，其中 N 可以是较小的维度。

在普通的 PC 或 MAC 上，如果您确保内部循环很快，您应该能够在几秒钟内用 C++ 或 Java 完成 1000x1000。