关灯问题(Lights Out) - Light chasing
有一个$n \times n$的方阵,每个位置上都有一盏灯。每次可以选择一个格子,选定后它与它相邻(有公共边)的格子的亮暗状态都会发生改变。现给定初始方阵中每盏灯的亮暗情况,请输出一个使所有灯都熄灭的方案。 该问题在wikipedia上的词条 Lights Out(game),尚未有中文页。 如有读者想验证自己的程序,可在LibreOJ提交,LibreOJ #6243. 关灯问题 。 初探 如果你有线性代数的相关知识储备,相信你此时已经意识到,该问题可以做如下的转换: 有$n^2$个开关,一共控制了$n^2$盏灯。同时,我们也已知每个开关所控制的灯集合。所以,只要将方程(一共$n^2$个,变量为每个开关的状态)列出,解决这个线性方程组便解决了这道题。 至于代码实现,不过是一个Gaussian elimination,写成记录异或路径的线性基也可,这个应该不是问题。甚至,对于某些原题自动机,可能已经找到了原题。 问题到这似乎已经解决,但是时间复杂度呢? 无论选择以上哪种实现,时间复杂度都在妥妥的$\mathcal{O}(\frac{n^6}{\omega})$。 $n$很小时,或许能够在$1s$内解决。例如这题,gym102920 J。 一个或许可行的方案 怎么办呢?无脑冲高斯消元似乎是不可能的了,那么,可以优化吗?于是,你开始注意到,这个系数矩阵似乎有点意思啊!(以$n=5$为例) $$ \left( \begin{matrix} C & I & O & O & O \newline I & C & I & O & O \newline O & I & C & I & O \newline O & O & I & C & I \newline O & O & O & I & C \newline \end{matrix} \right) $$...