费解的开关放在算法题库里是很多人第一次被二进制枚举卡住的地方。我第一次做时随手写了个DFS枚举25盏灯按还是不按两层递归跑样例倒是过了提交直接超时。后来才意识到这题要的不是深搜剪枝而是先想明白第一行的按法只有32种然后用二进制枚举把32种情况全列出来剩下的行全都由约束自动确定。这篇文章会把完整的思考过程重走一遍从暴力搜到二进制枚举从二维数组写到位运算压缩顺便把我踩过的几个坑都列出来。适合刚学完位运算、想做状压入门题找感觉的同学也适合把这道题当模板复习的选手。1. 题目到底在讲什么5x5灯阵的十字翻转规则1.1 题面、输入输出与约束条件原题给的是一个 5x5 的01矩阵1表示灯亮0表示灯灭。每次可以选择任意一盏灯按下按下这盏灯的同时它自己以及上、下、左、右相邻的灯状态都会翻转亮的灭灭的亮。也就是说一次操作的影响范围是一个十字形并且这个十字完全包含在5x5棋盘内时一共影响5盏灯如果在边界只影响3盏角上或4盏边上。目标是找到一种按灯方案使得最后25盏灯全部变亮输出最少按下次数如果答案超过6输出-1。T组测试数据过来时每组给你5行字符串每行是5个0/1字符读完就要输出这一组的答案。这类题看起来像BFS最短路径但状态空间有2^253350万种BFS直接爆内存看起来又像DFS找可行解但搜索树深度25、分支2直接暴力深搜在时间上也扛不住。提示题目里超过6步输出-1并不是普通的无解标志它属于题目本身的额外限制。需要先算出该组的最小步数再判断是否超过6。后面第5章会专门说这个坑。1.2 为什么按两次等于没按是整道题的基石灯的翻转是01异或操作。按两次同一盏灯等于对同一个位置做了两次XOR 1状态回到原点相当于什么都没做。所以在最优解里任何一盏灯被按的次数最多只能是一次。这个结论的价值在于把按灯方案从每次按哪盏灯、按几次的搜索问题变成了在25个位置中选择一个子集按下的组合问题。每个灯只有两种决策按或不按。于是全部方案恰好对应25位二进制数这也是后面所有状态压缩的合法性来源。1.3 这道题真正费解的地方不在翻转规则很多人读题之后觉得规则很简单不就是翻转上下左右嘛为什么能让人卡上一下午我自己的体会是卡点有三个按灯顺序这个抽象概念干扰了思考。其实因为最终状态只取决于哪些位置被按过跟按下顺序无关XOR满足交换律所以顺序是个伪问题。不知道枚举什么。看到5x5第一反应是全棋盘枚举2^25太大不枚举又找不到别的入口。这里缺的就是枚举第一行、剩余行递推的模型。缺少对约束传播方向的感知。棋盘按行处理时上一行的状态会约束下一行的操作这个约束一旦建立开关问题从搜索就退化成确定性问题了。这三点的本质都指向同一个突破口先枚举一行再把其余行的决策变成没有选择。接下来直接看为什么暴力搜索不可行。2. 暴力思路为什么行不通2^25和搜索树第一层决定一切2.1 直接DFS枚举25盏灯的规模估算先做一次成本估算。如果用DFS对25个位置做选/不选的分支整棵搜索树有2^25个叶子也就是33554432个状态。每到一个叶子要花大约25次翻转操作去模拟验证最终灯态总操作量是8.4亿级别在一般的评测环境下单组都快逼近时间上限何况题目还可能是多组输入。BFS按层搜最短路径更不现实光是保存所有去重后的状态内存就要按千万级的状态数来算直接爆炸。所以这道题其实在提醒我们遇到棋盘翻转题目先别急着往DFS/BFS里钻第一步应该寻找决策之间的耦合关系。灯与灯之间不是独立的你按这盏灯会改变周围灯的状态这种关联既是麻烦也是线索。2.2 关键观察除了第一行后面每行都没有自由意志手动推一个例子就会发现问题变成线性链条。假设我随便按了第一行的若干盏灯。这时第一行有的灯亮、有的灯灭。为了让第一行全亮我能动谁能影响第一行第j列的灯的因素只有三个第一行自身的第j列、第二行第j列以及第一行左右两盏。但左右两盏已经在第一行按它们反而会破坏第一行其它已经确定的灯所以正常情况下我们不希望在第一行里再增加额外操作。于是让第一行某盏灭灯变亮的唯一可靠方法就是在第二行的同一列按一次。注意这一按会联动第三行同列但不会影响第一行其它列也不会影响第二行左右两盏之外的状态判断。所以给定第一行的操作方案后第二行的操作列就全部锁定了。第二行处理完之后为了让第二行全亮又只能通过第三行的同列操作以此类推一直到第五行。第五行没有第六行可以借用所以第五行是否全亮就成为验证当前方案是否成功的唯一标准。当前处理行检查位置补救操作第1行处理完第0行第j列灭按(1, j)第2行处理完第1行第j列灭按(2, j)第3行处理完第2行第j列灭按(3, j)第4行处理完第3行第j列灭按(4, j)第5行检查第4行是否有灭灯有则方案失败这个链条意味着枚举第一行的32种按法即可因为每种第一行方案只会确定唯一一套后续行方案。2.3 为什么从上往下推而不是随便选一行枚举其实从下往上推也完全可行。把棋盘上下翻转约束关系同样成立。选第一行来枚举只是因为它天然方便按顺序处理而且从代码上看先读入第一行再逐层往下写循环结构最自然。如果你选中间某一行做自由变量那么上下两边都要分别递推代码会多不少边界判断但底层思维是一样的。这个观察也引出整篇文章的核心结论——搜索空间从2^25压缩到了2^532。压缩的关键不是剪枝是找到自由度和约束的分界。棋盘上有25个决策位但你一旦确定其中一行其余20个决策位置就都被唯一确定了。这20个位置不是可以选择怎么按而是必须按某些位置其余位置按了反而出错。3. 突破口用二进制枚举第一行的32种按法3.1 从5个开关到0~31的映射第一行有5盏灯每一种按法都可以表示成一个5位的二进制数。第0位表示第0列按不按第1位表示第1列按不按以此类推。state0表示第一行一盏都不按state31二进制11111表示第一行五盏全按。枚举时直接for (int state 0; state 32; state)每次循环对应一个完整的第一行方案。判断某一位是否被按下用(state j) 1为1则在第j列按下。这个写法的好处是枚举天然覆盖了选子集的全部情况每个state都对应一个唯一子集。3.2 第一行按完之后第二行起就是填空这里我把模拟过程拆成四步方便对应到代码第一步复制初始棋盘到临时数组保证每个state都从初始状态开始推而不是接着上一个state的残局继续推。第二步按二进制state模拟第一行按下操作。注意按第一行第j列时会翻转第一行第j列以及上下左右所以实际模拟时要考虑第二行同列可能提前被翻了一下。第三步从第二行开始逐行处理。查到上一行第j列的灯还是灭的就在当前行第j列按下。因为当前行按下会翻转上一行同列这一按正好把上一行的灭灯救活。这里有个细节在逐行处理过程中上一行所有位置一定会依次变成亮灯因为我们就是针对每个灭灯位置专门按了当前行的对应列。按当前行时还会影响当前行的左右灯和下一行的同列灯这些副作用都不用管因为它们要么在后续遍历时被处理要么被记录成方案的一部分。第四步处理完前四行后检查第五行状态。第五行如果全亮整个棋盘就全亮了第五行还有灭灯说明这个state不可能成功直接丢弃。3.3 为什么第一步的复制棋盘看起来多余却必不可少初写这题的人最容易在这里犯迷糊。如果不在每个state开头复制初始棋盘而是直接在原始棋盘上模拟那第一个state的按下操作会污染第二个state的起点最后统计出乱七八糟的结果。正确做法是每轮枚举从原始状态重新来一遍模拟过程全部作用于临时数组一轮结束之后把临时数组丢弃下一轮再重新复制。提示这个每轮重置初始状态的习惯在做搜索回溯和状压模拟时非常通用养成习惯能少踩很多莫名其妙的坑。4. 位运算实现把5x5棋盘压成5个整数4.1 为什么要做状态压缩用二维数组bool a[5][5]其实也能写代码逻辑和上面完全一致只是模拟翻转时要写五个格子的分支判断比较啰嗦。而把每行压成一个int之后翻转操作就是一次异或你不需要for循环去翻转5个格子只需要构造一个mask一行里所有受影响位置一次XOR搞定。比如按当前行第j列时受影响的是本行的第j、j-1、j1列上一行和下一行的第j列。那么按下的操作等价于三行各自的异或a[r] ^ mask其中mask包含第j、j-1、j1位a[r-1] ^ (1 j)如果r 0a[r1] ^ (1 j)如果r 4。一次操作从翻转5个格子变成了至多三次异或代码短了出错的面积也小了。4.2 完整代码实现#include cstdio #include cstring #include algorithm using namespace std; int T; int a[5]; void press(int r, int c) { a[r] ^ 1 c; if (r 0) a[r - 1] ^ 1 c; if (r 4) a[r 1] ^ 1 c; if (c 0) a[r] ^ 1 (c - 1); if (c 4) a[r] ^ 1 (c 1); } int main() { scanf(%d, T); while (T--) { for (int i 0; i 5; i) { char s[10]; scanf(%s, s); a[i] 0; for (int j 0; j 5; j) if (s[j] 1) a[i] | 1 j; } int best 0x3f3f3f3f; for (int state 0; state 32; state) { int cur[5]; memcpy(cur, a, sizeof(a)); int cnt 0; for (int j 0; j 5; j) if (state j 1) { press(0, j); cnt; } for (int r 1; r 5; r) for (int j 0; j 5; j) if ((a[r - 1] j 1) 0) { press(r, j); cnt; } if (a[4] (1 5) - 1) if (cnt best) best cnt; memcpy(a, cur, sizeof(a)); } if (best 6) printf(-1\n); else printf(%d\n, best); } return 0; }4.3 代码逐段解读与容易混淆的变量读取部分s[j] 1表示该位置亮把对应bit置1所以初始棋盘里1表示亮、0表示灭。一行最终读成一个五位的int比如10110会变成二进制10110对应的int。左右方向并不影响正确性原因在第5章细说。枚举部分for (int state 0; state 32; state)是32种第一行按法。注意这里的state只决定第一行不需要管后面几行后面几行的按法是在递推过程中按条件自动生成的。模拟部分press就是纯粹的异或模拟参数r、c表示当前按下的位置。它不关心你现在按完别人会不会坏掉因为XOR翻转本身就是对称的按键顺序也不影响最终结果。验证部分处理完前四行后第五行如果等于全1即(1 5) - 1说明方案成功。这里用表达式而不是写死31更稳也方便看代码的人立刻明白全亮的含义。最后整体判断best保存所有成功方案中的最小按下次数。只有全部state跑完之后才做best 6的判断。千万别在枚举过程中看到cnt6就break原因见5.5。我额外提醒一句memcpy(cur, a, sizeof(a))里的cur是本轮state的初始值快照必须在模拟前保存模拟后恢复。你也可以把press函数改成操作cur数组而不是全局a只要保证每次枚举从同一个初始状态出发即可。5. 排错与坑点照着思路写完后这五个地方最容易翻车5.1 漏掉每轮重置会让state之间互相污染具体场景state0第一行不按模拟完后棋盘已经被改得面目全非如果不恢复state1第一行按第0列会基于一堆残留状态继续推得到的结果毫无意义。我自己的第一版代码就是忘了恢复样例看着对实际上只是恰好前几个state相互抵消提交后WA得毫无头绪。5.2 递推判断写反是要看上一行还是当前行逐行处理时判断条件是a[r-1]的第j位为0不是a[r]的第j位为0。想清楚原因当前正在处理第r行目的就是把r-1行全救活所以看的是r-1行。如果你写成看当前行那结果大概率是谁都不亮调试时灯态一片混乱。5.3 位方向与全亮判断的对应关系读入时用1 j存储判断全亮用(1 5) - 1这里的第0位对应读入字符串位置的最左边还是最右边其实无所谓。因为问题里左右翻转操作是对称的把棋盘整体水平镜像一下全亮的目标不变翻转关系也不变所以最后位拼接的左右方向不影响答案。但是要记住存储、翻转、判断三个地方必须方向一致不要读入用1 j翻转判断却用1 (4 - j)那就会错位。5.4 输入是01字符不是整行数字每组输入是类似10110的字符串不是读入一个整数10110。直接用scanf(%d)会把一整行当作一个大整数在5x5的情况下数值能达到一万多位运算逻辑直接乱套。正确做法是按字符串读入逐字符处理。5.5 不要在枚举中途因为cnt6就break一个state在当前步骤已经超过6次按下后面只会增加不会减少所以理论上提前剪枝是安全的。但这里有个逻辑陷阱如果你在某个state里cnt6就break你就漏掉了这个state继续模拟的可能性——虽然这个state不可能成为答案但因为break后没有恢复状态下一个state起点也被污染了。更稳妥的做法是从不中途退出完整模拟完所有state最后统一比较。本题数据量极小32种全模拟没有任何性能压力没必要为了节约那一点计算引入状态污染风险。注意很多题解里说如果超过6步可以直接输出-1那是指已经找到更优解的前提下做的提前返回。对于练习我建议先写全模拟版本彻底跑通后再考虑优化。6. 举一反三什么样的问题适合枚举一行让步6.1 通法特征与适用范围费解的开关不是个例。棋盘类翻转题里有一大类都满足每次操作影响一个固定形状十字、九宫格、对角线等且操作是XOR自逆的目标是让整个棋盘变成某种目标状态。这类题最关键的一步都是先找出自由行/自由列——哪一行一旦确定其余行就不能自主决策了。判断方式很简单看操作的传播方向。如果一次操作影响的形状里包含下一行的同列位置那么就可以建立从上到下的约束链。因为处理第r行时第r1行会被波及而处理第r1行时第r2行又会被波及逐层传递最后某一行的状态成为验证条件。6.2 放到其他类似题上的拓展思路POJ 3279 Fliptile是同一套模型只是目标状态从全亮变成了全部为0还要求输出字典序最小的翻转方案。处理时枚举第一行状态不变只是判断条件从a[4] 全1改成a[4] 0。可以看到会做费解的开关那类题目多半也能很快上手。另外如果棋盘不是5x5而是N行M列第一行枚举量变成2^M当M不超过20左右时依然可行再大就要考虑高斯消元解法了。这也是这种枚举行思路的适用范围边界。6.3 从这题得到的思维模型我后来做状压DP、插头DP之类的题时会想起这道题它教会我的不是一个具体技巧而是一种先找自由度再找约束链的建模顺序。做题时不急着写代码先在纸上问哪些决策是可以自由做的哪些决策是被前面决策锁死的自由的那部分数量够不够小能不能枚举如果够小枚举加贪心的组合往往就是最优解。最后分享一个我个人的小习惯做这类棋盘翻转题时写完了先不提交自己构造两组最朴素的case——棋盘全亮以及只在角上放一个灭灯。棋盘全亮跑出来答案应该是0因为不需要按角上灭灯的状态可以拿纸笔手推几步再对照程序输出。这两个小case能快速暴露位运算方向错、边界判断漏、递推条件写反的问题。我当时就是靠这个习惯把费解的开关从抄题解变成真正自己写出来的。这道题现在看依然值得隔一段时间重做一遍每次都会有新的手感。