打开网易新闻 查看更多视频

枚举 — 熄灯问题：

熄灯问题 2 问题描述

有一个由按钮组成的矩阵, 其中每行有6个按钮, 共5行

每个按钮的位置上有一盏灯

打开网易新闻 查看精彩图片

问题描述

有一个由按钮组成的矩阵, 其中每行有6个按钮, 共5行

每个按钮的位置上有一盏灯

当按下一个按钮后, 该按钮以及周围位置(上边, 下边, 左 边, 右边)的灯都会改变一次

打开网易新闻 查看精彩图片

问题描述

如果灯原来是点亮的, 就会被熄灭

如果灯原来是熄灭的, 则会被点亮

在矩阵角上的按钮改变3盏灯的状态

在矩阵边上的按钮改变4盏灯的状态

其他的按钮改变5盏灯的状态

打开网易新闻 查看精彩图片

在下图中, 左边矩阵中用X标记的按钮表示被按下, 右边的矩阵表示灯状态的改变

打开网易新闻 查看精彩图片

与一盏灯毗邻的多个按钮被按下时, 一个操作会抵消另 一次操作的结果 第2行第3, 5列的按钮都被按下 第2行第4列的灯的状态就不改变

打开网易新闻 查看精彩图片

对矩阵中的每盏灯设置一个初始状态 请你写一个程序, 确定需要按下哪些按钮, 恰好使得所 有的灯都熄灭 X X X 输入:

第一行是一个正整数N, 表示需要解决的案例数

每个案例由5行组成, 每一行包括6个数字

这些数字以空格隔开, 可以是0或1

0 表示灯的初始状态是熄灭的

1 表示灯的初始状态是点亮的 7 输出:

对每个案例, 首先输出一行, 输出字符串 “PUZZLE #m”, 其中m是该案例的序号

接着按照该案例的输入格式输出5行

1 表示需要把对应的按钮按下

0 表示不需要按对应的按钮

每个数字以一个空格隔开

打开网易新闻 查看精彩图片

解题分析(1) 第2次按下同一个按钮时, 将抵消第1次按下时所产 生的结果 每个按钮最多只需要按下一次 各个按钮被按下的顺序对最终的结果没有影响 对第1行中每盏点亮的灯, 按下第2行对应的按钮, 就 可以熄灭第1行的全部灯 如此重复下去, 可以熄灭第1, 2, 3, 4行的全部灯

解题分析(2) 第一想法: 枚举所有可能的按钮(开关)状态, 对每个状 态计算一下最后灯的情况, 看是否都熄灭 每个按钮有两种状态(按下或不按下) 一共有30个开关, 那么状态数是2 30 , 太多, 会超时 如何减少枚举的状态数目呢? 基本思路: 如果存在某个局部, 一旦这个局部的状态被确定, 那么剩余其他部分的状态只能是确定的一种, 或者不多的n 种, 那么就只需枚举这个局部的状态即可

解题分析(3) 本题是否存在这样的 “局部” 呢? 经过观察, 发现第1行就是这样的一个 “局部” 因为第1行的各开关状态确定的情况下, 这些开关作用过后, 将 导致第1行某些灯是亮的, 某些灯是灭的 要熄灭第1行某个亮着的灯(假设位于第i列), 那么唯一的办法就 是按下第2行第i列的开关 (因为第1行的开关已经用过了, 而第3行及其后的开关不会影响 到第1行) 为了使第1行的灯全部熄灭, 第2行的合理开关状态就是唯一的 1

解题分析(4) 第2行的开关起作用后, 为了熄灭第2行的灯, 第3行的合理开关状态就也是唯一的 以此类推, 最后一行的开关状态也是唯一的 只要第1行的状态定下来, 记作A, 那么剩余行的情况就是确 定唯一的了 推算出最后一行的开关状态, 然后看看最后一行的开关起作 用后, 最后一行的所有灯是否都熄灭: 如果是, 那么A就是一个解的状态 如果不是, 那么A不是解的状态, 第1行换个状态重新试试 只需枚举第1行的状态, 状态数是2 6 = 64 13 有没有状态数更少的做法？ 枚举第一列, 状态数是2 5 = 32 执行次数: 64×5×6 vs. 32×6×5

打开网易新闻 查看精彩图片

具体实现

用一个矩阵 puzzle[5][6] 表示灯的初始状态

puzzle[i][j]=1: 灯(i, j)初始时是被点亮的

puzzle [i][j]=0: 灯(i, j)初始时是熄灭的

用一个矩阵 press[5][6] 表示要计算的结果

press[i][j]=1: 需要按下按钮(i, j)

press[i][j]=0: 不需要按下按钮(i, j)

15

press[0]里放着第1行开关的状态, 如何进行枚举呢?

可以使用六重循环:

for( int a0 = 0; a0 < 2; a0++ )

for( int a1 = 0; a1 < 2; a1++ )

for( int a2 = 0; a2 < 2; a2++ )

for( int a3 = 0; a3 < 2; a3++ )

for( int a4 = 0; a4 < 2; a4++ )

for( int a5 = 0; a5 < 2; a5++ ) {

press[0][0] = a0;

press[0][1] = a1;

press[0][2] = a2; ……

}

16

实现方案

根据上面的分析, 按钮矩阵的第1行元素的各种取值进

行枚举, 依次考虑如下情况:

枚举方式:

将按钮矩阵的第1行看作一个二进制数

通过实现++操作实现 17

000000

0 0 0 0 0 1

0 0 0 0 1 0

0 0 0 0 1 1

0 0 0 1 0 0

111111

实现方案

用一个68的数组来表示按钮矩阵:

简化计算数组下一行的值的计算公式

第0行, 第0列和第7列不属于PRESS矩阵范围, 可全置0

给定PRESS的第1行取值, 计算出PRESS的其他行的值

press[2][c]=(puzzle[1][c]+press[1][c-1]

+press[1][c]+press[1][c+1] + press[0][c]) %2

0<r<5, 0<c<7

打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片

总 结 枚举过程 enumerate( )

press[1][]中每一个元素表示一个二进制数0/1, 通过模拟 二进制加法方式实现枚举

需要处理进位 推测验证过程 guess( )

用68按钮矩阵来简化下一行按钮值的计算公式

根据press[1][]和Puzzle数组, 用公式来计算使得1-4行所 有灯熄灭的press其他行的值, 再判断所计算的press数 组能否熄灭矩阵第5行的所有灯