4x4棋盘翻转：状态压缩与位运算枚举的0ms解法

1. 从一道经典题说起4x4棋盘翻转到底难在哪第一次看到这个题目的时候很多人会觉得它平平无奇——不就是4x4的棋盘每次翻一个格子连同上下左右问最少几步全白或全黑吗暴力搜一下不就完了但真动手写起来你会发现坑比想象中多得多。这道题在算法练习圈里流传很广编号1753属于那种看起来简单、写起来抓狂、优化完拍案叫绝的典型代表。它的核心场景是这样的给你一个4x4的棋盘每个格子要么是黑色要么是白色。每次操作可以翻转一个格子同时它上下左右相邻的格子也会跟着翻转如果存在的话。目标是把整个棋盘变成纯黑或者纯白求最少操作次数。如果做不到输出Impossible。为什么这道题值得单独拿出来讲因为它同时踩中了三个非常关键的技术点状态压缩、位运算枚举、翻转顺序无关性。这三个点任何一个理解不到位代码要么写错要么超时。而一旦全部打通你会发现这道题可以用0ms跑完快到评测机都来不及反应。这篇文章适合谁看如果你正在学状态压缩DP或者对位运算不够熟练又或者你写过这道题但总是WAWrong Answer那这篇内容就是为你准备的。我会从最朴素的思路讲起一步步推到0ms的解法把每一步的为什么都掰开揉碎。哪怕你之前没接触过状态压缩跟着走也能完全吃透。先说结论这道题的最优解不是DP而是枚举第一行的翻转状态共16种可能然后逐行递推。听起来简单但里面的位运算技巧和边界处理才是真正拉开差距的地方。下面我按实际调试的顺序把整个思路演进过程完整还原一遍。2. 核心思路拆解为什么枚举第一行就够了2.1 翻转顺序无关性——这道题的第一把钥匙很多人卡在第一步翻转的顺序到底影不影响结果答案是不影响。原因很简单翻转操作满足交换律。你先翻A再翻B和先翻B再翻A最终每个格子被翻转的次数是一样的。而且每个格子最多只需要翻一次——翻两次等于没翻翻三次等于翻一次。这个性质极其重要它意味着我们只需要关心哪些格子被翻了而不需要关心按什么顺序翻的。这个性质直接砍掉了搜索空间里一大半的冗余。如果没有这个认知你可能会去写BFS把每种棋盘状态当作一个节点每次翻转产生新状态。4x4棋盘有2^1665536种状态BFS理论上能跑但代码复杂、内存开销大而且完全没必要。提示翻转类题目几乎都有一个共性——操作可交换、幂等做两次抵消。抓住这一点很多看似复杂的搜索问题都能降维成枚举问题。2.2 逐行递推的连锁反应——第二把钥匙既然顺序无关那我们就可以人为规定一个处理顺序从上往下一行一行地确定每个格子要不要翻。关键观察来了当你处理到第i行时第i-1行的状态已经无法再被改变了因为能影响第i-1行的操作只有三种——翻第i-1行自己、翻第i-2行、翻第i行。前两者已经确定所以第i-1行最终是什么颜色完全取决于第i行怎么翻。这就形成了一个强约束第i行的翻转方案必须能把第i-1行修正成目标颜色。换句话说一旦第一行的翻转方案定了后面每一行的翻转方案都被唯一确定了。第一行有4个格子每个格子翻或不翻共2^416种可能。我们只需要枚举这16种对每种方案递推到底检查最后一行是否满足条件然后取操作次数最少的那个。这个思路的妙处在于它把2^16的搜索空间压缩到了2^416次枚举每次递推只需O(16)的时间总复杂度O(16×16)O(256)常数级别0ms轻松拿下。2.3 状态压缩——把棋盘塞进一个整数4x4棋盘一共16个格子每个格子只有黑白两种状态天然适合用一个16位整数表示。比如用1表示黑色0表示白色或者反过来看个人习惯。第r行第c列的格子对应整数的第(r*4c)位。这样整个棋盘就是一个0到65535之间的整数翻转操作就变成了异或运算。翻转某个格子本质上就是把它自己和上下左右对应的位取反。我们可以预先算出每个位置翻转时对应的掩码mask也就是一个16位整数哪些位需要变哪些位不变。之后每次翻转只需要state ^ mask[pos]一行代码搞定比操作二维数组快得多也不容易写错下标。这里有个细节要注意掩码的计算要考虑边界。比如左上角(0,0)的格子它没有上方和左方的邻居掩码里就只有它自己、右边(0,1)和下方(1,0)三个位。如果无脑把上下左右都算进去越界的位会污染其他行的数据导致结果完全错误。我见过太多人栽在这个边界处理上。3. 位运算实操掩码计算与状态表示3.1 棋盘状态的读入与编码输入是4行字符串每行4个字符b表示黑色w表示白色。我习惯用1表示黑色0表示白色。读入的时候逐字符判断如果是b就把对应位置1。int state 0; for (int i 0; i 4; i) { string line; cin line; for (int j 0; j 4; j) { if (line[j] b) { state | (1 (i * 4 j)); } } }这里用i*4j作为位下标第0行占位0-3第1行占位4-7以此类推。这样行和列的信息都编码进去了后面取某一位或者判断某一行是否全黑全白都很方便。3.2 翻转掩码的预计算对每个位置(r,c)计算翻转它时影响的位。上下左右四个方向用方向数组遍历判断是否越界不越界就把对应位加进掩码。int mask[16]; int dr[] {-1, 1, 0, 0}; int dc[] {0, 0, -1, 1}; for (int r 0; r 4; r) { for (int c 0; c 4; c) { int m 1 (r * 4 c); // 自己 for (int d 0; d 4; d) { int nr r dr[d]; int nc c dc[d]; if (nr 0 nr 4 nc 0 nc 4) { m | (1 (nr * 4 nc)); } } mask[r * 4 c] m; } }这段代码是整个解法的基础务必理解透彻。掩码的本质是翻转这个位置会波及哪些位用位或把所有受影响的位合并起来。之后无论棋盘当前是什么状态翻转操作都是统一的异或。注意掩码一旦算好就是固定的和当前棋盘状态无关。所以可以放在循环外面预计算一次避免重复计算。这是性能优化的一个小细节虽然这道题数据量小影响不大但养成习惯对写更复杂的题有好处。3.3 用异或实现翻转有了掩码翻转操作就是一行state ^ mask[pos];异或的性质决定了某位是1就变0是0就变1正好对应翻转。而且异或满足交换律和结合律多次翻转的结果和顺序无关完美契合题目性质。这就是为什么位运算和翻转类题目是天生一对。我实测下来用位运算比用二维数组模拟翻转代码量少了将近一半而且几乎不会出现下标越界的bug。唯一需要注意的是位下标的映射关系要统一别这里用r*4c那里用c*4r那就全乱了。4. 完整实现流程从枚举到判定4.1 枚举第一行的16种翻转方案第一行有4个格子每个格子翻或不翻用0到15的整数表示。第k位为1表示第一行第k个格子要翻。int ans INF; for (int first 0; first 16; first) { int cur state; int steps 0; // 应用第一行的翻转 for (int c 0; c 4; c) { if (first (1 c)) { cur ^ mask[c]; // 第一行第c列位下标就是c steps; } } // 后续行递推... }这里第一行的位下标是0到3因为第0行占位0-3第c列正好是位c。这个对应关系要记牢后面递推的时候会反复用到。4.2 逐行递推修正上一行处理完第一行后从第二行开始每一行的翻转方案由上一行的状态决定。具体来说对于第r行r从1到3检查第r-1行的第c列如果它是白色0假设目标是全黑那第r行第c列必须翻才能把它变成黑色。for (int r 1; r 4; r) { for (int c 0; c 4; c) { int prevBit (r - 1) * 4 c; if (((cur prevBit) 1) 0) { // 上一行这一列是白色 cur ^ mask[r * 4 c]; // 翻当前行这一列 steps; } } }这段逻辑是整道题的核心。为什么翻当前行能修正上一行因为当前行的翻转会影响上一行同列的格子上下相邻。而上一行自己已经不能再翻了翻了会破坏更上面的行所以只能靠当前行来补救。这就是逐行递推的精髓。4.3 最终判定与答案更新递推完所有行后检查最后一行是否全黑。如果全黑说明这个方案可行更新最小步数。bool ok true; for (int c 0; c 4; c) { if (((cur (12 c)) 1) 0) { // 最后一行第c列 ok false; break; } } if (ok) ans min(ans, steps);最后一行占位12-15所以位下标是12c。如果最后一行全黑方案成立。注意这里只检查最后一行因为前面的行在递推过程中已经被保证修正成黑色了。4.4 处理全白目标题目要求全黑或全白都算成功。上面的逻辑是奔着全黑去的。要处理全白最简单的办法是把棋盘状态取反0变11变0再跑一遍同样的逻辑。因为全白等价于取反后的全黑。// 第一遍目标全黑 // 第二遍state取反目标全黑等价于原棋盘全白取反操作用state ^ 0xFFFF即可16位全部翻转。两遍跑完取最小值如果还是INF就输出Impossible。5. 常见问题与排查技巧实录5.1 为什么我的答案总是差1或者多1这是最常见的bug十有八九是steps计数出了问题。要么是某个翻转漏加了要么是重复加了。我的建议是每次执行cur ^ mask[...]之后立刻steps把这两行绑在一起写不要分开。分开写很容易在某个分支里忘了加。另一个可能的原因是第一行枚举时first的位和列的对应关系搞反了。first (1c)对应的是第c列不是第c行。因为第一行只有一行位下标0-3就是列下标。这个如果搞混枚举的方案就全错了。5.2 边界掩码算错导致结果离谱掩码计算是重灾区。我见过有人把方向数组写成8个方向把对角线也算进去了结果翻转影响范围变大答案自然不对。记住题目说的是上下左右只有4个方向不含对角线。还有人忘了判断越界直接m | (1 (nr*4nc))当nr或nc是-1或4的时候位下标会变成负数或者超出范围行为未定义。一定要加if (nr0 nr4 nc0 nc4)这个判断。5.3 最后一行判定写错最后一行占位12-15有人写成(cur (3*4c))这其实是对的因为3*412。但如果写成(cur (4*4c))就错了那是第16位往后根本不存在。建议直接用常量12或者写个辅助函数getBit(state, r, c)减少出错概率。5.4 常见问题速查表问题现象可能原因排查方法答案偏大steps重复计数检查每次翻转后是否只加一次答案偏小漏算某些翻转检查递推循环是否覆盖所有行输出Impossible但实际有解掩码边界错误打印掩码二进制检查部分用例通过部分失败全白情况未处理确认是否跑了取反后的第二遍结果随机变化位下标映射不一致统一用r*4c全局检查实操心得调试这类位运算题目最有效的方法是把state打印成4x4的矩阵每一步翻转后都打印一次肉眼对比。比盯着二进制数字看高效得多。写个print函数五行代码能省你半小时。6. 性能优化与进阶思考6.1 为什么能跑到0ms这道题的理论复杂度是O(2^4 × 4 × 4) O(256)实际上就是几百次位运算现代CPU一微秒都用不了。评测机显示的0ms是因为计时精度不够实际耗时远小于1ms。所以这道题不存在性能瓶颈怎么写都能过。但能过和优雅是两回事。用位运算的写法代码短、逻辑清晰、不易出错这才是推荐它的理由。如果换成BFS或者DFS代码量翻倍还容易TLE虽然这道题数据小不会得不偿失。6.2 如果棋盘变成5x5或者更大呢有人会问如果棋盘不是4x4而是NxN这个思路还成立吗答案是成立但复杂度会变。枚举第一行需要2^N种可能每种递推O(N^2)总复杂度O(2^N × N^2)。N4时是256N5时是800N10时就是十万级别N20就爆炸了。所以这个枚举第一行逐行递推的方法适合N比较小的情况一般N≤10。如果N更大就需要用高斯消元或者更高级的状态压缩DP。但那是另一个话题了这道题用不上。6.3 状态压缩DP的另一种写法严格来说这道题也可以写成DP。定义dp[i][mask]表示处理到第i行第i行状态为mask时的最小步数。转移的时候枚举第i1行的翻转方案使得第i行被修正。但这样写状态数多、转移复杂实际跑起来还不如直接枚举第一行快。所以对于这道题枚举第一行是最优解不是DP。标题里说状态压缩DP其实更准确的说法是状态压缩枚举DP的成分很淡。我个人的看法是不要为了套DP而套DP。哪种方法简单高效就用哪种这才是工程思维。这道题的最优解就是枚举硬写成DP反而画蛇添足。6.4 一个容易被忽略的优化提前剪枝虽然这道题不需要剪枝也能0ms但如果想养成好习惯可以在枚举时加个判断如果当前steps已经大于等于ans就不用继续递推了直接跳过。这个剪枝在N更大的时候能省不少时间。if (steps ans) continue; // 放在递推循环里每次翻转后判断不过对于4x4来说这个剪枝意义不大因为总共就16种方案每种最多16步全跑完也就256次操作。加不加都一样快。但思路值得记住以后遇到搜索空间大的题目剪枝是救命稻草。7. 我在实际调试中踩过的坑第一次写这道题的时候我信心满满地用了BFS把每个棋盘状态当作节点结果内存超了。后来改用枚举第一行又因为掩码边界没处理好WA了好几次。最坑的一次是最后一行判定我把位下标写成了(cur (3*4c)) 1看起来没问题但实际上我前面读入的时候用的是i*4j第3行第c列确实是12c逻辑是对的。问题出在我取反处理全白的时候忘了重新初始化ans导致第二遍的结果覆盖了第一遍的。还有一次是steps计数我在第一行枚举的循环里加了steps但在递推循环里忘了加结果所有方案的步数都少了后面几行的翻转次数答案自然全错。这种bug最难查因为逻辑看起来完全正确就是数字对不上。后来我养成了一个习惯每次写cur ^ mask[...]下一行必须紧跟steps形成肌肉记忆再也没错过。另外一个经验是先把目标定成全黑跑通了再处理全白。不要一上来就想着两种目标一起处理那样逻辑会乱。分开跑两遍代码清晰调试也容易。等两种都跑通了再考虑能不能合并但通常没必要因为跑两遍也就多几微秒。最后分享一个小技巧如果你实在调不出来就把所有16种第一行方案的中间过程全部打印出来包括每一步的state和steps然后手动模拟一种方案看看代码的输出和你手算的是否一致。不一致的地方就是bug所在。这个方法笨但极其有效我靠它定位过好几个隐蔽的位运算错误。这道题虽然小但把状态压缩、位运算、枚举递推这几个核心技能都串起来了。把它彻底吃透以后再遇到类似的翻转类、棋盘类问题你会有一种一眼看穿的感觉。那种感觉就是刷题最大的乐趣所在。