1. 从熄灯问题看枚举与位运算的配合逻辑熄灯问题是很多算法入门者绕不开的一道经典题它看起来像是一个简单的开关游戏但真正动手写起来很多人会在第一版代码里写出六层嵌套循环然后发现要么超时要么逻辑根本跑不通。我在带新人做这道题的时候最常听到的反馈就是我知道要用枚举但不知道枚举什么。这个问题的核心矛盾在于棋盘上每个灯的状态由它自己和上下左右四个方向的开关共同决定如果无脑枚举所有开关的组合复杂度是2的30次方完全不可行。所以这道题真正的价值不在于枚举本身而在于如何把枚举的范围从30个开关压缩到只剩一行。一旦想通这个压缩逻辑再配合位运算来做状态压缩和快速翻转整个代码可以从上百行缩到几十行而且跑起来非常干净。这篇文章我会从枚举策略的推导讲起把为什么只需要枚举第一行这件事掰开揉碎说清楚然后给出位运算版本的完整实现最后聊聊我在调试这类题目时踩过的几个坑。适合阅读这篇文章的人正在学C、刚接触枚举和位运算、做过熄灯问题但没完全理解其中逻辑的开发者。如果你已经能独立写出位运算版本也可以看看后面关于边界处理和调试技巧的部分说不定有你能用上的细节。2. 熄灯问题的规则拆解与枚举策略推导2.1 游戏规则的精确定义先把规则说清楚不然后面推导容易出歧义。熄灯问题通常是这样描述的有一个5行6列的灯阵每个灯有亮和灭两种状态。每盏灯旁边都有一个开关按下一个开关会翻转它自己以及上下左右相邻灯的状态亮变灭、灭变亮。目标是通过按若干开关让所有灯都变成灭的状态。这里有几个容易搞混的点需要提前明确按开关的顺序不影响最终结果因为翻转操作满足交换律先按A再按B和先按B再按A结果一样。同一个开关按两次等于没按按三次等于按一次。所以每个开关只有按和不按两种有效选择。边界上的灯没有四个方向的邻居比如角落的灯只有两个邻居翻转时只翻转存在的邻居。注意有些版本的熄灯问题目标状态是全亮而不是全灭这两种在实现上只是初始状态取反的区别逻辑完全一样。本文以全灭为目标。2.2 为什么暴力枚举所有开关行不通5行6列一共30个开关每个开关两种状态总组合数是2^30大约是10.7亿种。就算每种组合用位运算在常数时间内验证10亿次操作在现代机器上也要跑好几秒甚至更久而且这还只是一组测试数据。如果题目有多组输入直接超时。那能不能用贪心或者动态规划贪心不行因为按下一个开关会影响多个灯局部最优不等于全局最优。动态规划的状态设计也很别扭因为灯的状态是二维的而且翻转操作会跨行影响。所以这道题的标准解法还是枚举但关键是要找到枚举的维度可以压缩这个突破口。2.3 关键洞察第一行确定后后续行被迫确定这是整道题最核心的一步推理我把它拆成三个层次来讲。第一层第一行的开关怎么按完全自由。第一行有6个开关每个可以按或不按一共2^664种可能。这个数量很小完全可以枚举。第二层第一行按完之后第二行的开关就被第一行的灯状态逼出来了。为什么因为第一行的灯只受三个地方影响第一行自己的开关、第二行对应位置的开关、以及第一行左右邻居的开关。当第一行的开关确定之后第一行每个灯的当前状态就只差第二行对应开关这一个变量了。如果第一行某个灯现在是亮的而它左右邻居和自身开关都已经固定那么唯一能改变它的就是第二行同列的开关。所以第二行同列的开关必须按下去否则这个灯永远亮着。第三层同理第二行确定后第三行被迫确定一路推到第五行。最后只需要检查第五行的灯是否全灭。如果全灭说明这个第一行的按法是一个合法解如果有亮着的灯说明这个第一行按法无解。这个推理链把2^30的搜索空间压缩到了2^664复杂度直接降到可以忽略不计。我第一次理解这个逻辑的时候感觉就像多米诺骨牌——推倒第一张后面的全跟着倒。2.4 枚举策略的伪代码框架把上面的推理写成伪代码结构非常清晰for 第一行的每一种按法 (0 到 63): 把第一行按法应用到棋盘上 for 行 1 到 4: for 列 0 到 5: if 当前行第列灯是亮的: 按下下一行同列的开关 检查最后一行是否全灭 if 全灭: 输出解这个框架里按下开关这个操作会被频繁调用如果每次都用循环去翻转五个位置代码会很长而且容易写错边界。这就是位运算登场的地方。3. 位运算在熄灯问题中的三个具体用途3.1 用整数表示一整行的灯状态5行6列的棋盘每一行有6个灯正好可以用一个整数的低6位来表示。第0位表示最左边的灯第5位表示最右边的灯1表示亮0表示灭。这样一行就是一个0到63之间的整数。比如一行灯的状态是亮灭亮灭亮灭用二进制表示就是101010也就是十进制的42。这种表示方式的好处是整行的状态可以用一个变量存下来翻转操作可以用位运算批量完成不需要逐个灯去改。3.2 用异或实现翻转操作翻转一个灯的状态在二进制层面就是把它对应的位取反也就是异或1。如果我们要翻转某一行的某些位只需要构造一个翻转掩码然后和原状态异或即可。按下第r行第c列的开关会影响五个位置第r行第c列自己第r行第c-1列如果存在第r行第c1列如果存在第r-1行第c列如果存在第r1行第c列如果存在对于同一行内的翻转可以用一个掩码来表示。假设按下第c列的开关那么这一行需要翻转的位是第c-1、c、c1位在边界处要处理越界。这个掩码可以预先算好也可以现场用移位构造。// 按下第c列开关时对同一行的翻转掩码 int rowMask (1 c); if (c 0) rowMask | (1 (c - 1)); if (c 5) rowMask | (1 (c 1));对于上下两行只需要翻转第c位int colMask (1 c);这样一次按键操作就变成了三次异或当前行异或rowMask上一行异或colMask下一行异或colMask。比循环翻转五个位置快得多代码也短得多。3.3 用位运算提取和检查灯的状态在推导过程中我们需要判断当前行第c列的灯是不是亮的。用位运算就是if (board[row] (1 c)) { // 这个灯是亮的 }检查最后一行是否全灭就是判断这个整数是否等于0if (board[4] 0) { // 找到解了 }这两个操作都是O(1)的比数组遍历快很多而且写起来更简洁。3.4 位运算版本相比数组版本的优势对比对比维度数组版本位运算版本状态存储5×6的二维数组5个整数翻转操作循环处理5个位置需判断边界3次异或掩码预处理好状态检查遍历6个元素一次与运算代码行数约80-100行约40-50行调试难度边界容易写错掩码逻辑清晰易验证运行速度较慢极快我在实际写的时候位运算版本从构思到跑通大概花了二十分钟而第一次用数组写的时候调了一个多小时主要时间都花在边界判断上。所以如果你还在用数组硬写强烈建议换成位运算的思路。4. 完整代码实现与逐段解析4.1 整体代码结构先给出完整代码然后逐段解释。#include iostream using namespace std; int main() { int board[5]; // 读入初始状态每行一个整数1表示亮0表示灭 for (int i 0; i 5; i) { board[i] 0; for (int j 0; j 6; j) { int x; cin x; if (x) board[i] | (1 j); } } // 枚举第一行的64种按法 for (int first 0; first 64; first) { int cur[5]; for (int i 0; i 5; i) cur[i] board[i]; // 应用第一行的按法 for (int c 0; c 6; c) { if (first (1 c)) { // 按下第0行第c列 cur[0] ^ (1 c); if (c 0) cur[0] ^ (1 (c - 1)); if (c 5) cur[0] ^ (1 (c 1)); cur[1] ^ (1 c); } } // 逐行推导后续按法 for (int r 0; r 4; r) { for (int c 0; c 6; c) { if (cur[r] (1 c)) { // 第r行第c列灯亮按下第r1行第c列 cur[r 1] ^ (1 c); cur[r] ^ (1 c); if (c 0) cur[r 1] ^ (1 (c - 1)); if (c 5) cur[r 1] ^ (1 (c 1)); if (r 2 5) cur[r 2] ^ (1 c); } } } // 检查最后一行 if (cur[4] 0) { // 输出第一行按法 for (int c 0; c 6; c) { cout ((first c) 1) ; } cout endl; break; } } return 0; }4.2 输入处理与状态初始化输入部分我选择逐位读入然后拼成整数。这里有个细节题目给的输入通常是0和1的矩阵我用cin x读入每个数如果是1就把对应的位置1。这样读完之后board[i]就是一个6位的整数第j位对应第j列的灯。提示如果你的输入格式是每行一个字符串比如010101可以用string s; cin s;然后遍历字符串来构造整数逻辑是一样的。4.3 第一行枚举与状态复制外层循环for (int first 0; first 64; first)枚举第一行的所有按法。first的第c位为1表示按下第0行第c列的开关。每次枚举都要把原始棋盘复制一份到cur数组因为我们要在副本上做翻转操作不能破坏原始状态。这个复制操作是必须的我见过有人直接在原数组上改结果第二次枚举的时候状态已经乱了。4.4 逐行推导的核心循环for (int r 0; r 4; r)这个循环处理第0行到第3行对每一行检查每个灯。如果第r行第c列的灯是亮的就按下第r1行第c列的开关。按下这个开关会影响第r1行第c列自己第r1行第c-1列左邻居如果存在第r1行第c1列右邻居如果存在第r行第c列上邻居也就是当前这个亮着的灯第r2行第c列下邻居如果存在代码里对应五行异或操作。注意if (r 2 5)这个判断因为最后一行没有下一行不能越界。4.5 最后一行验证与结果输出推导完前四行的按法之后第五行的状态已经确定了。如果cur[4] 0说明所有灯都灭了找到了一个合法解。输出第一行的按法即可因为后续行的按法是由第一行唯一确定的。这里我选择输出第一行的按法因为这是最简洁的解表示。有些题目要求输出完整的5×6按法矩阵那就需要在推导过程中把每行的按法记录下来最后一起输出。5. 调试熄灯问题时最容易踩的四个坑5.1 位序方向搞反导致左右颠倒这是我最开始写位运算版本时踩的坑。我用1 c表示第c列但心里想的是从左到右第c列而实际上如果输入是从左到右读的1 0对应的是最左边。结果左右邻居的掩码写反了c-1和c1搞混导致所有解都错。排查方法拿一个只有最左边灯亮的简单输入手动推导应该按哪些开关然后看代码输出是否一致。如果左右颠倒一测就露馅。5.2 边界列的邻居掩码越界当c0时1 (c-1)就是1 -1这是未定义行为。虽然很多编译器会把它当成移位31位或者0但结果不可预测。所以必须加if (c 0)的判断。同理c5时不能加右邻居。我见过有人用(1 (c-1)) 0x3F来避免越界但这样在c0时会把第5位也翻转逻辑就错了。老老实实加if判断最稳妥。5.3 忘记复制棋盘导致状态污染前面提过每次枚举第一行按法时都要从原始状态复制一份。如果直接在原数组上操作第一次枚举之后棋盘状态就被改了后续枚举全部基于错误的状态。这个bug很隐蔽因为第一次枚举可能就找到解了你根本发现不了。建议在复制之后加一句断言或者打印确认每次枚举开始时棋盘状态一致。5.4 最后一行验证时忽略了中间行有些人只检查最后一行是否全灭但忘了中间行在推导过程中已经被处理过了。实际上推导过程保证了前四行在每一步都被清零所以最后只需要检查第五行。但如果你在推导循环里写错了条件比如漏掉了某个方向的翻转可能导致中间行还有亮灯但最后一行恰好全灭这时候输出的是错误解。验证方法找到解之后把完整的按法矩阵应用到初始棋盘上手动模拟一遍确认所有灯都灭了。这个验证步骤在调试阶段非常值得做。6. 从熄灯问题延伸出的枚举压缩思路熄灯问题教会我的最重要的一件事是枚举不一定要枚举所有变量可以枚举一部分剩下的通过约束推导出来。这个思路在很多题目里都能用。比如经典的开关灯变种问题如果目标不是全灭而是某个特定图案同样可以枚举第一行然后逐行推导只是最后验证的条件变了。再比如一些二维填充问题如果每一行的选择会唯一决定下一行的选择都可以套用这个框架。另一个延伸方向是用位运算做状态压缩的动态规划。熄灯问题里我们用整数表示一行的状态这个技巧在状压DP里是基础操作。比如蒙德里安的梦想这类问题就是用整数表示一行的填充状态然后做状态转移。把熄灯问题吃透再学状压DP会轻松很多。还有一个值得思考的点是为什么是枚举第一行而不是枚举第一列因为题目是5行6列枚举第一行是2^664枚举第一列是2^532后者更小。所以如果行列数不等应该枚举较小的那一维。这个优化在数据范围更大的时候很有用。我在实际做题时如果遇到类似的按开关影响邻居的题目第一反应就是找有没有可以逐行推导的约束。如果有就枚举第一行如果没有再考虑其他方法。这个思维习惯帮我省了很多时间。