灭灯游戏学习笔记
Querainy
·
·
个人记录
参考 : https://github.com/njpipeorgan/LightsOut/tree/master
这里的灭灯游戏是这样一个奇奇怪怪的东西 :
一个n\times n的、每个位置有一个灯和按钮的棋盘，一开始有一些灯亮着，每次可以选择一个按钮按下去，这会让这个位置和它上下左右的灯改变状态——亮着的熄灭，熄灭的亮起。找一种方式熄灭所有灯。
显然有以下几条 :
-
对于有一个按钮按超过一次的方案，一定有一种方案与它等价，并且每个按钮最多按一次。这相当于我们只需考虑每个按钮最多按一次。
-
如果确定了第一行按了哪些按钮，我们可以这样进行模拟，判断第一行的方案是否可行 : 我们假设已经处理完前i-1行，对于第i行，每个在i-1行亮着的灯下面那个按钮都要被按(因为没有其它还需要考虑的按钮可以影响这个灯了)，其它按钮都不应该被按。如果最后一行全部熄灭，说明第一行方案可行。
首先显然可以枚举第一行(列)状态并向下模拟进行检验。复杂度O(2^nn^2)。
考虑把每个位置拿出来，发现i,j位置的状态只跟自己和周围按钮和自己一开始的状态有关，因此可以列一个异或方程。设a_{i,j}表示初始状态，f_{i,j}表示i,j是否按下，可得 :
f_{i,j}\oplus f_{i-1,j}\oplus f_{i+1,j}\oplus f_{i,j-1}\oplus f_{i,j+1}\oplus a_{i,j}=0
举个例子，这是在3\times3棋盘上的方程 :
\begin{aligned}
f_{1,1}\oplus f_{2,1}\oplus f_{1,2}\oplus a_{1,1}=0\\
f_{1,2}\oplus f_{2,2}\oplus f_{1,1}\oplus f_{1,3}\oplus a_{1,2}=0\\
f_{1,3}\oplus f_{2,3}\oplus f_{1,2}\oplus a_{1,3}=0\\
f_{2,1}\oplus f_{1,1}\oplus f_{3,1}\oplus f_{2,2}\oplus a_{2,1}=0\\
f_{2,2}\oplus f_{1,2}\oplus f_{3,2}\oplus f_{2,1}\oplus f_{2,3}\oplus a_{2,2}=0\\
f_{2,3}\oplus f_{1,3}\oplus f_{3,3}\oplus f_{2,2}\oplus a_{2,3}=0\\
f_{3,1}\oplus f_{2,1}\oplus f_{3,2}\oplus a_{3,1}=0\\
f_{3,2}\oplus f_{2,2}\oplus f_{3,1}\oplus f_{3,3}\oplus a_{3,2}=0\\
f_{3,3}\oplus f_{2,3}\oplus f_{3,2}\oplus a_{3,3}=0
\end{aligned}
那么我们可以直接对这个东西做高消，复杂度O(n^6/w)(w是字长)(但是我觉得可以做到接近O(n^4)?)。甚至不知道能不能跑n=20。
考虑把两个做法结合起来。我们只把第一行的按钮情况设出来，并从上往下模拟，得到最后一行每个灯熄灭的条件。设A_{i,j}表示i,j在按完前i行后的状态，F_{i,j}表示i,j是否需要按下。首先，显然有 :
\begin{aligned}
F_{1,i}&=f_{1,i}\\
A_{1,i}&=F_{1,i}\oplus F_{1,i-1}\oplus F_{1,i+1}\oplus a_{1,i}
\end{aligned}
根据模拟式子，我们有
\begin{aligned}
F_{i,j}&=A_{i-1,j}\\
A_{i,j}&=F_{i,j}\oplus F_{i-1,j}\oplus F_{i,j-1}\oplus F_{i,j+1}\oplus a_{i,j}
\end{aligned}
那么用一个bitset存储，我们可以在O(n^3/w)时间内计算最后一行的A，其中w是字长。然后根据模拟的正确性，不管第一行如何选择，我们总能让除最后一行都变成全灭，那么只需要让最后一行的所有A=0，此时使用高消解出f_{1,1},...,f_{1,n}，就可以构造出一种方案。
再举个例子，如果我们有一个矩阵是这样的 :
\left[\begin{array}
{ccc}
0 & 1 & 0\\
1 & 0 & 1\\
1 & 0 & 1
\end{array}\right]
那么
\begin{aligned}
F&=\left[\begin{array}
{ccc}
f_{1,1} & f_{1,2} & f_{1,3}\\
f_{1,1}\oplus f_{1,2} & f_{1,1}\oplus f_{1,2}\oplus f_{1,3}\oplus 1 & f_{1,2}\oplus f_{1,3}\\
f_{1,1}\oplus f_{1,3} & 1 & f_{1,1}\oplus f_{1,3}
\end{array}\right]\\
A&=\left[\begin{array}
{ccc}
f_{1,1}\oplus f_{1,2} & f_{1,1}\oplus f_{1,2}\oplus f_{1,3}\oplus 1 & f_{1,2}\oplus f_{1,3}\\
f_{1,1}\oplus f_{1,3} & 1 & f_{1,1}\oplus f_{1,3}\\
f_{1,2}\oplus f_{1,3} & f_{1,1}\oplus f_{1,2}\oplus f_{1,3} & f_{1,1}\oplus f_{1,2}
\end{array}\right]
\end{aligned}
然后进行高消，解得f_{1,1}=f_{1,2}=f_{1,3}=0，则可以构造如下的方案 :
\left[\begin{array}
{ccc}
0 & 0 & 0\\
0 & 1 & 0\\
0 & 1 & 0
\end{array}\right]
实现中F可以省去。
总时间复杂度O(n^3
/w)，空间复杂度O(n^3/w)，可以滚动数组到O(n^2/w)。不知道有什么方法可以做到更优。
归类为主元法。