算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。
熄灯问题
Loading...
来自 Peking University 的课程
算法基础
294 个评分
Explore Related Videos
At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you
从本节课中
枚举
在日常生活中我们经常遇到这样的情景：数字密码最后一位忘记了，就从0~9逐个尝试；去提货点取快递，快递员检查完所有包裹才找到属于你的；警察列举出所有的嫌疑人才有可能发现真凶…以上在进行归纳推理时，逐个考察了某类事情的所有可能情况，并逐一进行检验，这种方法叫做枚举。枚举比较直观，易于理解，本模块将介绍枚举算法的基本数学模型和常用策略，从而解决通过公式推导、规则演绎的方法不能解决的问题。PS：我们这门课程一直处在不断地建设与优化当中，吸取了很多以往课程的经典视频，所以如果你看到视频中出现了不同课程的名字，也不要惊讶哦，因为你正在集百家所长：）
与讲师见面
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
大家好，在这一小节中呢，我们来看一个关于枚举算法 的一个具体的例题，称为叫做“熄灯问题”。
那么这个熄灯问题到底讲的是什么呢？我们来具体看一下。
那么熄灯问题的问题描述呢，是这样子的
我们有一个由按钮组成的矩阵 这个矩阵呢每一行包含了这样6个按钮
而这个矩阵呢同时有这样5行
也就是说，我们有一个这样子5*6的一个按钮矩阵
那么对于这个按钮来讲呢，它的每一个位置上
都有一盏对应的灯，这个灯呢 那么当你按下其中相应的一个按钮的时候，那么这个
按钮及其周围，啊，比方说上边、下边、
左边以及右边，那么一共有5盏灯，都会发生一次改变，原来这个灯呢
是亮的，那么它就会被熄灭；如果 原来这个灯本身是熄灭的，那么它就会被重新地来点亮，也就是说你按下一次按钮
这个当前按钮所在位置的灯及其周围的 这4盏灯都会发生一次改变。
当然了，如果这个按钮本身所处在这个矩阵的位置发生不同的话呢，
不同的话呢，那么相应它改变的灯的盏数呢也会不一样。
我们看到如果你的这个按钮位于矩阵的这个
角上，啊，不管是4个角的哪一个角，那么它都会相应地去改变这3盏灯 对应的状态。
那么如果呢，这个按钮恰好按在这个边缘上，也就是只有对应的这样4盏灯 会发生改变。
那当然除了这个角上和边上这种特殊情况之外，如果你正好
按在其他位置上的按钮，那么对应就会改变5盏灯。
我们看到说呢，如果对应
这样一张图，我们左边这个矩阵中间的这3个相应的位置
就画X的这个位置的按钮呢都被同时按下的话，那么右边的这个矩阵中间
相应位置，比方说对应这是第1个按钮按下的
将会发生这3盏灯的改变；相应第2盏灯
第2个按钮被按下，会引起这样5盏灯发生改变； 那同样
第3个按钮按下之后呢会引起这样4盏灯的状态发生改变，也就是说在左图当中，
左图当中，所有都是熄灭状态的灯，通过按下这3个按钮之后呢
那么就会产生相应状态的变化，有这样一批灯呢，就会被点亮了。
那么，我们会看到呢，如果1盏灯的周围的多个按钮
按钮被多次按下之后，也就是说1盏灯周围的按钮被多次按下
那么一个操作会抵消另外一个操作，什么意思呢？也就是说我们如果
以这个第2行中间的第3列和第5列的按钮
被按下为例，是吧，当第3，第3列这个按钮被按下之后，理论上呢，它周围的这
5个灯都会发生改变，啊，原来 暗的呢变成亮的，原来亮的呢变成了暗的。
所以对于第4列的这一盏灯来讲，理论上应该是由亮变暗，啊，也就是被熄灭掉了。
但是呢，因为 我第5列的灯，按钮呢又再次被按下，所以原先这个熄灭的
第4列的灯呢就会被重新地点亮，因此我们看到当
这个第2行的第3列和第5列的按钮被同时作用的时候
那么与它毗邻的这个第4盏灯实际上最后的结果就是发生状态并不改变。
那么我们就证实我们刚才提到的说，一个多，一个灯呢这个毗邻的
多个按钮被操作时呢，那么一个操作会抵消另外一个操作。
所以呢，对于我们当前这个问题，它实际上呢
呢就是对于矩阵中间的每一盏灯
去设置了一个初始的状态，啊。也就是说它已经有一个亮着或者暗着的状态
那么希望我们去自己写一个程序，来确定说，如何去按下
按下某些按钮，使得呢之前这个初始状态中间
有亮有暗的这些灯呢全部被熄灭掉。
那么这个程序应该怎么写呢？我们首先来看一看对于这个程序的输入的一些数据
这个输入数据呢，实际上有这么几个具体的数据来组成，首先就是第一行是由
一个正整数N，那么这个N呢它就表示说需要
解决的这个案例，属于说包含了几个case需要处理。
那么对于每一个案例来讲呢，它都是由一个5行的这个
具体的值来组成，那么每一行中间呢又包含了6个数字，把分别对应这个5*6的一个矩阵
那么这些数字本身呢它是以空格相隔开的，那么具体每个值呢
非0即1，啊，其中呢0就是表示灯的初始状态是熄灭的
而1呢，是表示它是点亮的，也就是说这个矩阵中间包含的数字就正好描述了
我的这个当前灯的初始状态，0就是指熄灭，1就表示的是点亮。
那么相应，啊，通过我们去设计一个程序之后呢，希望得到这样的
一个输出，对于每一个案例，是吧，刚开始我们不是输入了一个N作为案例的个数吗
那么相应的输出呢我们就会针对每一个案例给出这样的，首先给出这样的一行
是“PUZZLE #M”，啊也就是说，m是相应的这个案例的序号
对于每一个对应m的案例，那么我们需要把这个相应的这个
呃，输出的这个 方式呢也认为是5行，但是这个5行的这个矩阵呢，它中间的这个1表示的是说
表示的是说相应的这个按钮是要按下，也就是说你要按下这个按钮，而0呢
则表示说不需要按下相应的按钮，也就是这个输出的这个矩阵描述的是对于
某一个特定案例中间按钮是否需要进行处理，进行操作这样的一个描述。
具体样例的一个输入，是吧，我们看到说这有一个2
那么2首先描述的就是我的这个当中包含了有
那么两个不同的案例，啊，每一个案例中间呢，有这么一个5行6列的一个
矩阵，这个矩阵呢由不同的0、1来描述当前灯的初始状态
那么同样地，最后我们希望给出的这个输出呢就是针对不同的这个
呃样，案例；啊，那么分别给出一个对应的矩阵，这个
矩阵描述的呢，是我们如何对这个按钮矩阵进行操作 那么1就是按下，0就是不按。
那么在了解了这个样例的输入和输出之后呢，我们就来具体看一看
这个题目本身应该怎么样去处理，才能有效地设计好 一个关于这个按钮操作的一个程序。
那么我们通过题面，已经看到说呢，我们对于这样的一个熄灯问题，你会发现说
我们第2次按下同一个按钮，也就是说对于同一个按钮，按两次
那么它将会去抵消掉第一次按下时所产生的结果。
那么因此我们就可以看到得出这样的一个结论，我们对于每一个按钮，其实
最多只需要按下一次，是吧？也就是说如果我按下了两次，那么相当于什么都没有做
所以我们只需要去做一次操作就可以了。
其次呢，就是各个按钮被按下的顺序对最终的结果是没有影响的啊。
以及呢，第三点就是我们对于第1行中间的每一盏点亮的灯
那么如果这时候你去按下第2行之中间对于的按钮
那么它将会熄灭第1行中间的全部灯，啊，因为第1行
的灯受到第2行的影响，那么当你第2行
对应按下相应第1行中间还仍然亮着灯的时候，那么第1行就可以
通过第2行按钮的操作来实现全部熄灭这样的一个工作。
那么如此反复重复下去，是吧，我们刚才通过按第2行
去熄灭了第1行，那么这里我们就可以继续通过按第3行去熄灭第2行
以及按第4行去熄灭第3行，通过这样一系列的操作可以
依次去熄灭每一行中间的全部的灯。
那么，直观的想法呢，当然会是想到说，对于这样的一个按钮
进行这个一一按下或者是不按的操作的这样的一个过程呢
我们可以通过枚举所有的按钮可能的情况来进行判断
也就是说，我们把每一种状态下，也就是开关设置的情况呢一一地罗列
出来进行枚举，完了之后看一看说，通过对应这样一系列操作之后
它是否能够使得最后灯全部被熄灭？啊，也就是说看看说在对应
罗列的各个情况下是否能够使得最后灯熄灭，获得这个问题的求解？
那么我们会看到，在我们这个问题当中呢
每一个按钮对应都由两个状态
按下或者是不按，也就是说非1即0 那么我们一共有5*6，30个开关
也就是说，我们要一一列举这种状态的话呢，需要执行2的30次方
这个数量实在是太大了，对吧？那么我们在做POJ的时候经常有同学会suffer这样的问题，也就是说
什么time limit over吧？我们经常会感到超时，也就是说我们设计的程序
本身呢已经远远大过了我们当前这个允许的范围。
那么现在这个问题呢，显然不是要能够用这个2的30次方这样的一个枚举
过程来解决的；那么对于这样的一个问题，我们要怎么样能够进一步去减少枚举
的这个状态数目，才是问题的关键，是吧，我们就说我们只需要去列举其中的一部分
就可以获得本身问题的解答。
那么涉及这个题目的基本思路，实际上呢 就是去看说我们是否能去枚举一个局部。
所谓这个局部呢，也就是它局部的状态一半被确定了
那么剩余其他的状态，啊，其他部分与之对应的状态呢
也就是确定了一种，或者是不多的n种，那么这个时候
我们就只需要去枚举这个局部的状态就可以了。
所以，我们看到说呢，如果一个问题本身它的这个局部的状态一旦确定了
那么其相应的剩余的其他状态呢是非常少的几种情况，或者是一种情况。
而我们需要做的呢，只是去简单地枚举一下这 有几种这样简单的局部的状态出现就可以了。
所以通过这样的一个分析呢，我们关键问题就是要去考虑说
我们这个题目本身是否存在这样的一个“局部”呢
这个局部呢，实际上通过观察和分析，我们刚才就已经发现到了
第1行实际上就可以认为是一个所谓的“局部”
为什么这么讲呢？我们来进一步看，因为我们发现说呢，对于第1行的这个各个开关的
状态如果一旦确定下来的话，那么通过这个开关作用过后
导致第1行中间的灯是亮是暗已经是确定的。
什么意思呢？就是说我的这个题目输入进来的时候第1行的灯是有一个初始的状态的，对吧？那么
对于这个初始的状态呢，我对于当前的第1行的按钮可能有一些操作，比如说按下
或者是不按，那么对于这个初始状态通过这样第1行的操作作用完之后
那么可能还有一些灯呢是亮的，还有一些灯呢是灭的。
那么第1行已经全部操作完之后，我们如果
希望去熄灭掉第1行中间的某个亮着的灯
比方说我们在这里假设第i列是吧，第1行的第i列
这个灯它本身已经对于第1行的操作已经结束了
那么如果你希望去熄灭第1行中间对应的这个第i列上面仍然亮着的灯的话
那么唯一的办法是什么？是按下相应 第2行中间第i列这个开关
对吧？因为第1行的开关呢已经用过了，不能再用了
而第3行及其以后的开关呢又影响不到第1行
每一个开关只能影响周围，这样上下两个或者是左右两个对应的位置，啊
因此我们说，当你要去熄灭第1行
中间亮的灯，且第1行已经操作过了 那么唯一的办法就是去操作第2行中间相应的开关。
那么为了使第1行的灯全部熄灭，那么 第2行的合理开关的状态呢就是唯一的。
所以我们说，对应的第2行的这个开关
起作用过后呢，那么为了熄灭第二行的灯
相应的第三行的合理开关状态也是唯一的，跟刚才第一，第二行一模一样
那么以此类推，啊，直到到了最后一行的开关状态因为它的这个
最后一行比方说是第五行在我们这个例子当中，那么由于第五行开关的状态呢要去
使得第四行中间所有亮着的灯被熄灭，因此第五行的这个开关的操作呢
也是唯一确定的，所以我们说当第一
行的状态定下来之后，记作是A，那么
剩余行的情况其实都是相应唯一的，没有
什么其他可选的，为了使得第一行全部熄灭，第2行必须这么干
那么第2行已经做了这些操作之后呢，就使得第2行的灯的状态也被定下来了
那么为了使得第2行的灯全熄灭呢，第3行也被迫只能去操作相应 对应亮的灯的位置。
因此我们说这个时候，我们只需要去
推算最后一行的开关状态，是吧
最后一行的开关起了作用之后，那么它当然一定会使得第四行，也就是说前一行的灯
全部熄灭，那么关键它又是同时是最后一行，那么最后一行是否能够在所有的开关起完作用之后
都被熄灭掉呢？ 如果它是的，它可以使得所有灯被熄灭，那么我们就说
当前的那个局部状态A就是一个解的状态。
那么否则的话呢A就不是一个解的状态，我们需要去对第一行这个局部状态呢
换一个状态去试一试，啊重新的去尝试一下，所以我们说我们实际上只需要去枚举
这个A的不同状态，就可以最终简单获得问题的解，所以刚才那个
2的30次方呢，就可以简化成通过只枚举第一行的状态来获得
那么简化后的这个状态数呢实际上也被这个减小
为只需要去测试成2的6次方，也就是说64种状态 就可以获得问题的解。
当然如果你更贪心一点是吧，当然在我们这个问题当中其实并不是很复杂，对比不是很强烈
我们就会想说有没有什么更小的办法使得这个状态数
考虑的更少呢，那当然也可以去考虑从列开始是吧
我们可以认为说呢如果从列开始的话呢，那么状态数是2的5次方
也就是32个可以少掉一半，啊，我们可以按列来枚举的话呢
就可以使得执行的这个次数呢是这个32*6*5这样的一个方式.
那么我们来看看具体的实现，啊，我们去
具体用程序去实现的时候呢，我们通常要去设计
几个举证，去描述状态是吧，比如在我们这个题目当中呢我们要设计一个叫做puzzle的一个举证
那么用一个二维的数组来表示灯的初始状态，这个灯的初始
状态呢，如果是1，啊，就是被点亮，如果是0就是熄灭。
接着呢我们还要去用设计一个举证press,用这个press这样的一个二维数组呢
去表示这个计算的结果，也就是说当这个press这个具体的这个值是1的时候呢
就表示要按下这个按钮，如果是0呢，就表示不需要按下，啊，不需要按下
我们看到那么我们说了我们在这个
简化后的这个，简，枚举局部状态这样的一个解法当中呢
我们实际上是要去枚举第一行开关的状态，那么对于
第一行开关来讲如何进行枚举，其实也是有所考虑的
最简单的我们当然可以直接去使用这个六重循环，啊，也就是说我们使得利用这样的
嵌套的六个for循环去便利说每一个开关都有0，1这样的一个不同的状态
那么对于六个开关呢又有相应的不同的这样的组合，通过这样的
六重循环呢，构建这个第一行开关当中的这
64个状态，是吧，64个状态，那么实际上呢我们后来进一步去
分析说我们除了去利用这样的六重for循环进行这个一一枚举之外呢
实际上我们也可以去利用这个第一行元素中间各个值，各个这种
取值的这个具体的状态来进行，啊，比如说我们这边看到我们实际上可以利用这个
啊，把第一行每一个取值呢看成是一个二进制数
这个二进制数呢依次会使得每一个位呢
通过++来进行不断的累加，当然是从左往右了
我们会看到依次通过++这个操作呢使得这个数二进制数呢不断的增大
来进一步获得第一行元素中间每一个枚举的过程，也就是说我们把这64个
状态映射成一个二进制数来进行
表达，那么通过这个二进制数不断地进行这个
变化累加1的这样的一个操作，逐一列举整个第一行的一个状态
那么通过这样的一个描述呢，可能会比二进制数的这个实现呢，就是通过刚才那个比2，比刚才的那个
啊，6重循环呢来得看起来要更加简洁和明了一些。
那么我们在具体实现的时候呢，还可以有这样的一个小策略
也就是我们刚才呢看到我们的这个，呃，按钮矩阵和这个
呃，初始这个状态矩阵呢，都是这个按理论上说呢，都是5x6的对吧，5行6列
但是呢我们在程序设计的时候，可以选取一个6x8
的数组来存放相应的这个按钮矩阵
这样会有一个好处就是本来呢我们对于这个角上的点，或者是对于这个边上的点
都需要再重新写一个相应的操作来进行完成，因为它和在这个当中取的
某一个按钮的这个操作呢可能会有些不一样，是吧？因为一个是只处理了3盏灯，一个是处理了4盏灯
那么都不同于处理5盏灯，那么如果我们假设呢对于这个
矩阵外面呢再扩充一圈出来，啊,扩充这样一圈
那么这一圈的出现呢可以使得说我的这个程序当中呢
就使，只需要使，写一个这样子最传统的包含
5个元素的这样的一个操作，就可以囊括所有的情况。啊，所以呢
在这个例子当中呢，我们会看到我们利用一个6*8的数组，把这个原有的这个
呃，矩阵呢的左上 右呢全部扩充成一圈，啊。扩充一圈呢，这它实际上是不属于
本身PRESS这个矩阵的，我们就可以把它全置为是0，啊，全置为是0。
那么有了这样的操作可以进一步简化我们这个程序设计的这个过程。
那么之后我们就来看，我们实际上呢对于 给定PRESS的这个第1行的取值，啊，给定，也就是说我们对于第1行如果已经
确定了第1行PRESS的方式，那么实际上对于其他行的这个PRESS值呢
是固定的，啊，比方说以这个我们给出一个核心的这段代码
为例，我们看到说呢，当我们知道这个第
我们要获得第r+1行
以及第c列所相应位置是否要进行按或者不按
那么它的计算是由谁来得到的呢？那么它就是由相应的第r行
第c列对应这个灯的状态，啊，是暗或者是亮的状态
加上相应的这个第r行和c-1列，也就是它对应同一行的
前面一列以及相应的这个位置r
c 的这个位置的操作和它相应同一行的
这个右边一列的操作，以及这个 r c 当前这个r
c位置上的前一行r-1行的相应的PRESS的值，也就是说通过对于
这个当前行和列上相应周围一圈的所有操作
来看它们去
取模，是吧，模2，看一看说
我最后是需要在这个r减，r+1行
第c列上是否需要操作，是吧？如果说你原来的这个初始值
通过周围所有这些前些行的所有的操作，最后累计的结果呢
是暗的，也就是0，那么我当前这个PRESS呢就不需要按；
如果你是1，那么我就需要也相应的摁下一下，使得你这个
啊,r+1，r和c的，就是对应第r行第c列的这盏灯呢被
熄灭掉。啊，所以这就是我们看到说只要固定了第一行的取值
那么PRESS的其他行的值呢是可以相应被这样计算出来的。
我们来看看具体的程序实现。
那么在通过我们上，刚才的上述的分析之后，我们会看到实际上呢
我们最核心的程序就是这个guess，是吧
我们在有了这个两个6x8的矩阵press和puzzle之后，啊一个puzzle是存的初始状态，
press是存的是否要按下的一个这个，呃，开关的这个操作。
那么我们就来guess一下，说看一看当前这个枚举的状态是否能够满足将所有的
这个对应的灯全部熄灭这样的一个过程。啊，在我们这个，guess这个函数当中呢
它包括了两部分，第一部分，啊第一个这样的两个for循环它所做的
事儿是什么呢？它就是根据你已经给定的press的第一行
以及puzzle数组去计算相应的这个press其他行的值，啊，也就是说
我们刚才在前页中间看到的这个press的计算。我们依次去便利
相应的行和列，那么去计算什么呢？去计算说
在给定了当前puzzle的第2行第c列的
puzzle的值之后，那么通过其他行的这些操作已经确定下来的这个
操作之后，我们看一看说，我当前的这个r+1行，第c列的这个
按钮是否需要被按下。
那么一旦确定了所有的这个被按下的这个按钮之后，那么直到最后一行，啊，也就是说
这个press第5行所对应的值，那么就到了这个第2个for循环，就是说
我们依次推出了每一行press都是什么样的值，那么
每一行press定下来之后，它的前一行就被相应的把灯
熄灭了，直到第5行，啊，第5行去熄灭了第4行之后
那么我们会看到我们要去判断第5行操作结束之后
第5行的灯是否也被全部熄灭了呢？因此我们要让这个
第5行中间的每一列被循环到，是吧？column从1, c 从1一直到小于7，那么c不断地++
那么它所做的事儿呢就是去判断一下说第5行中间的
每一个值，啊，也就是我对应的这个第5行的
puzzle[5][c]，啊。第5行中间的某，第c列它是否
和我前面所有做的操作后的这个结果是一致的？啊，如果这个操作
那么比如说对于它当前这个第5行第c列左边的这个按钮按下，以及它
自身的这个按钮和它右边这个按钮，以及它上面的这个按钮，因为第5行是没有下面这个按钮的，是吧，我们对
这4个按钮同时操作完之后，那么如果它是和当前的这个
第5行中间的这个灯的状态是一致的，也就是说如果我的灯本身是亮着的
并且呢通过你刚才一系列的操作之后，它仍然也是使得按下的 那么这个灯就会被熄灭。
那么如果原来这个puzzle[5][c]是，本身就是暗着的，而通过你刚才一系列操作之后呢
累加的结果是不做任何操作，那么它也是被
变成是暗着的；那么如果说这样的一个if判断它是成立的
也就是说，它没有，是不等的，是吧？那么也就是说我当前的这个
啊状态A，第一行所对应的这个状态呢是false的，我们需要去更新新的状态，否则
的话呢，那当然是return ture啦，也就是说我们发现说我们之前找到的这个A的局部状态
就是我们所希望的求解的这个状态，是吧？所以这个guess函数中间呢就包含了这样的两部分
第一部分就是去计算相应的press的这个矩阵当中其他行的一个确定的值
最后呢是对于 已知的这个press数，数组，看看它是否能够
去熄灭第5行，也就是最后一行中间的所有灯 如果它确实能够熄灭，那么我们这个guess就返回一个true
啊也就是说，我们认为说我们这个枚举的尝试是能够获得 问题的解的。
那么，有了这个guess之后，我们就要进一步看一看说我们实际上呢
在这个过程当中，枚真正做的枚举的就是这个enumerate
那么enumerate呢它是用来枚举了谁呢？它枚举的实际上是第1行元素的
状态，啊第一行；那么在这个例子里面我们会看到说呢
我们实际上 首先呢，应该是让第1行的初始状态全部为0，是吧
全部为0，我们因为说了我们考虑用二进制数来去描述
我们当前的这个第1行依次的状态，那么这64种状态呢实际上
就是通过我的二进制数不断地移位累加的这样一个过程所实现的。
那么我们在这个while循环当中呢就是去 判断这个guess函数返回的是否为false
如果它返回的是false,也就是说我们没有找到当前这个状态能够解决
问题本身，那么我们就继续去更新下一个所要
枚举的第一行的元素，啊我们在这个while循环当中会看到
我们实际上呢对应就是让这个press这个[1][1]这个值呢
不断地去累加，啊去做这个加1的这样的一个的工作，那么当你加
也就说，加了一之后，我们就会去判断一下说你是否是大于1的，
因为是一个二进制数嘛，非0即1，当你如果大于1的话呢，实际上就要形成一个
啊，进行进位这样的工作啊，这段代，这个，在这个
小的 while 循环当中其实它做的事呢，就是一个累加进位的值
的一个判断吧，当你发现当前这个位置呢它是大于1了，啊，变成了,2
那么这个时候我们就要让当前的这个第一行第 C 列的这个值呢
变回是1，那么变回1之后呢，就意味着就要把这个进上来这个位呢，放到它前一个位上来，
啊，前一个位上来，就是说，我们如果当你这个时候在这个位置上加了1，啊，我们就会发现说呢，
我们之前相应的这个值就会变成为2，那么为2之后我们在二进制数里头是不允许有2存在的，
因此呢，我们就需要把这个相应的位进到上面来，所以这时候 C 要
++，啊，那么这个时候就是原来这个值呢，就变为了是0，然后
进位加上来之后呢，这个值又变成了是2，啊，那么我们依次，依旧要去进行这个
啊，进位。所以这个时候我们会看到说呢，press
第一行，第 C 列呢也要++，那么就是 C++
，也就是把相应的这个 呃，对应的这个列数呢不断的扩大，那么相应的这个进位呢，就可以来进行实现了。
所以我们看到说呢，在这个 while 循环里头，它做了两件事，一个就是让这个
相应的这个第一行的这个二进制状态的这个数
不断的进行加一，那么加一了之后呢，我要去通过这个进位
来实现说我不断的去改变相应的这么一
系列状态的这么一个工作，那么在 enumerate 这样的一个
呃，枚举的 函数确定好之后，那么这个程序呢，实际上就非常的简单了，我们会
看到我们在主程序当中呢，实际上就是首先会定义了一系列的这个
啊，int 型的这个变量，啊，有 cases ，i，r，c，那么分别代表的是
等于是 cases 输入的是第一行啊，我们说首先要输入有几个案例数
完了之后呢，我们会依次的把这个
press 中间的 中间的我们刚才看到那一圈是吧，那个相应的值都把它赋为是0，
完了之后呢，我们会 把对应的这个中间实际上对应的那个5乘6，
的矩阵中间的这个初始值都放到这个 puzzie 的这个
数组里头去，就是说读入输入的数据， 那么读入好输入数据之后呢，我们就去调用
相应的这个 enumerate 这个枚举的这个函数。
那么当然在 enumerate 这个函数当中呢，最关键就是我们每一次都在 while 循环判断这个 guess 是不是能够获得当前的这个解的状态。
如果不是呢，我们就要去更新我们对应的这个第一行的状态，
那么直到你找到了最后的这个问题的解，比如说如何 press
相应的这个 这个开关为止，之后呢我们就可以 print 按照题目要求必须要输出
puzzle 这个 number 有了 puzzle number
之后呢，我们就相应的去输出每一个 press 数组中间对应的值，
当然要注意就是因为这个 press 也是我们定义的是一个6乘8的一个矩阵。
所以我们要让这个 press 是从1开始然后分别 r 是小于6 c
是小于,7，那么这实际上呢，就是我们整个去求解这个熄灯问题的一个主的程序。
那么最后小结一下，小结一下我们这个熄灯问题的这个过程，
我们看到对于这个程序设计当中呢，有一个最关键的一个枚举过程， 过程，称它叫做
enumerate 这个函数，这个函数本身呢，重点是说 我们在对于第一行的这个
press 的这个数据来进行处理的时候，我们把每一个元素，
都表示成了一个二进制数来进行枚举，那么枚举的过程呢，我们是去模拟了一个二
二进制的加法，啊，我们去通过不断的去累加然后去处理进位来实现，
我们这个 enumerate 生成不同第一行的初始状态的这样的一个过程，
接着呢，我们会看到说呢，在这个 enumerate 里头其实嵌套的去判断，
判断呢，是否这个，通过 guess 这个函数来验证说，
通过第一行状态确定之后我们的一系列操作能否将所有的，
灯熄灭这样的一个过程，那么我们在这里头呢实际上用了一个6乘8的按钮矩阵，
来简化每一行中间按钮的这个计算的公式，也就是说它统一变成了一个，
呃，统一的这样的一个操作，那么我们给出了一个这样 press 的一 press
的一个表达的一个公式，也就是说我们只要给定相应的这个， puzzle
的这个值那么我们就可以去计算相应， 它后一行对应的位置上是否需要去按这个开关，啊，
我们根据这个 press 第一行和 puzzle 整个数组，就
就可以去计算相应一到四行所有灯熄灭的时候， press
的值到底应该是多少，啊，那么最后 最后我们要做的事就是我们已经确定好了整个
press 数组， 我们要看一看这个 press
数组它时候能够去熄灭掉矩阵的第5行的灯， 那么如果它能够熄灭的话，那么自然这就是通过
guess 这个函数我们所找到的问题的解， 那么这就是关于我们举的第一个枚举的小例子，熄灯问题。
