java算法点灯_点灯游戏的O(n^3)算法

点灯游戏简介

一层大楼共有

个房间，每个房间都有一盏灯和一个按钮。按动一个房间的按钮后，这个房间和周围四个相邻的房间的灯的状态全部都会改变(由暗变为亮或者亮变为暗)。目标是通过按按钮把所有的灯都点亮(默认情况下全暗)。

点灯游戏规律

我们不难发现以下规律

1. 按偶数次按钮相当于没有按。

2. 无论按按钮顺序如何结果总是一样的。

因此我们有以下结论

1. 对于盘面上的每一个按钮，我们只需要考虑其按开或关的状态。

2. 每一个按钮的状态都是互相独立的，不需要考虑按按钮的顺序。

点灯游戏算法概览

1. 完全穷举法，

2. 首行穷举法，

3. 完全方程法，

4. 首行方程法，

点灯游戏算法详解

1.完全穷举法，

对于每一个按钮只有开和关两种状态。而一旦所有按钮的状态都确定了，灯的状态也就确定了。因此，我们只需要把所有按钮的所有可能的状态列举出来，算出对应灯的状态并判断所有灯是否都点亮了即可。

不难发现，一个按钮的状态是

种，因此x个按钮的状态就是

种。一个

的房间一共有

个按钮，因此就有

种状态。这种算法的复杂度就是

。

举个例子，下面是一种房间按钮的状态和对应灯的状态(■ 代表开，□代表关，●代表亮，○代表暗)：

■ □ ■ □ ■ ● ● ● ● ●

□ ■ □ ■ □ ● ● ● ● ●

■ □ □ □ ■ ● ● ○ ● ●

□ ■ □ ■ □ ● ● ● ● ●

■ □ ■ □ ■ ● ● ● ● ●

下面是另一个例子：

■ ■ □ □ □ ○ ○ ○ ○ ○

□ □ ■ □ □ ○ ○ ○ ○ ○

■ □ ■ ■ □ ○ ○ ● ○ ○

■ □ □ □ ■ ○ ○ ○ ○ ○

□ ■ ■ □ ■ ○ ○ ○ ○ ○

这是合并后的结果(

下的解)：

□ ■ ■ □ ■ ● ● ● ● ●

□ ■ ■ ■ □ ● ● ● ● ●

□ □ ■ ■ ■ ● ● ● ● ●

■ ■ □ ■ ■ ● ● ● ● ●

■ ■ □ □ □ ● ● ● ● ●

有些情况下，即使按了按钮，全部灯的状态也可能不变：

■ □ ■ □ ■ ○ ○ ○ ○ ○

■ □ ■ □ ■ ○ ○ ○ ○ ○

□ □ □ □ □ ○ ○ ○ ○ ○

■ □ ■ □ ■ ○ ○ ○ ○ ○

■ □ ■ □ ■ ○ ○ ○ ○ ○

因此，解可能不是唯一的(对于解的存在性，唯一性及解的个数，将在算法3中讨论)：

■ ■ □ □ □ ● ● ● ● ●

■ ■ □ ■ ■ ● ● ● ● ●

□ □ ■ ■ ■ ● ● ● ● ●

□ ■ ■ ■ □ ● ● ● ● ●

□ ■ ■ □ ■ ● ● ● ● ●

2.首行穷举法，

完全穷举法的时间复杂度太高，当

时，房间的状态已高达

种。在游玩的过程中我们会去尝试点亮尽可能多的灯。很多状态(例如只按

或

个按钮)显然无法满足我们的要求而可以快速排除。

为了使得尽可能多的灯被点亮，假设我们已经决定了第一行按钮的状态，此时只有第一行和第二行的灯被改变了。由于只有第一行或第二行按钮会改变第一行灯的状态，为了使得第一行的灯全亮，由于第一行按钮状态已经确定，我们只能去按第二行的按钮，此时第二行按钮开的状态和第一行灯灭的状态是相反的(为了让第一行灯亮，我们必须去按第二行对应列的按钮)，此时第二行的按钮状态也被确定了。

由于第二行按钮状态确定了，为了使第二行灯全亮，第三行按钮的状态也被确定了。以此类推，整个房间的按钮都被第一行按钮的状态确定了，而房间里除了最后一行的灯也都是全亮的。

因此，其实我们不需要把房间里所有的按钮可能的状态全部列举出来，而只需要把第一行按钮可能的状态列举出来就行了。对于每一种状态，我们只需要按照上面的步骤计算出后面

行的按钮状态，然后计算出最后一行灯的状态就行了。对于房间里可能出现的别的按钮的状态的可能性，由于前面

行的灯不是全亮所以不需要考虑。

一行里的灯一共有

个，因此就有

种状态。这种算法的复杂度就是

。

举个例子，假设第一行按钮的状态是：

■ □ ■ □ □

则按钮和灯的状态为：

■ □ ■ □ □ ● ○ ● ● ○

□ □ □ □ □ ● ○ ● ○ ○

□ □ □ □ □ ○ ○ ○ ○ ○

□ □ □ □ □ ○ ○ ○ ○ ○

□ □ □ □ □ ○ ○ ○ ○ ○

因此，为了让第一行第二列和第五列的灯亮，必须按第二行第二列和第五列的按钮：

■ □ ■ □ □ ● ● ● ● ●

□ ■ □ □ ■ ○ ● ○ ● ●

□ □ □ □ □ ○ ● ○ ○ ●

□ □ □ □ □ ○ ○ ○ ○ ○

□ □ □ □ □ ○ ○ ○ ○ ○

然后是第三行第一列和第三列的按钮：

■ □ ■ □ □ ● ● ● ● ●

□ ■ □ □ ■ ● ● ● ● ●

■ □ ■ □