最近在OJ讨论区刷到一道被戏称为“吓哭全世界80亿人”的奇异题两个阵营在一张棋盘上反复拉扯要求把所有合法的排布方案全部数出来。听上去很简单——不就是枚举所有情况吗有人真的写了二重循环套递归结果数据一大直接超时评论区一片哀嚎。这道题本身不算难但把“无脑列举”四个字体现得淋漓尽致。我花了两个晚上从暴力枚举一路改到剪枝回溯最后AC的时候忍不住想写一篇复盘。这篇文章就聊聊这道智斗题的完整思路、C实现和一堆踩坑记录适合已经掌握基础递归、想真正搞懂暴力枚举边界和优化方向的读者。1. 先看懂题这题到底在“智斗”什么1.1 题目原型与输入输出题目背景可以抽象成这样一个棋盘问题给一个 N 行 M 列的棋盘每个格子可以属于“光阵营”或“暗阵营”。两个阵营互相较劲规则是谁也不允许在某条对角线上连续占 K 个格子。问在 N×M 个格子上一共有多少种合法的阵营分配方案。输入就是三个整数 N、M、K其中 N 和 M 都不大但乘积可能达到 16 或者 20。输出只需要方案数并且一般会要求对 1e97 取模。因为答案可能大到离谱比如 K 很小的时候差不多每种染色方案都合法方案数接近 2^(N×M)这个数字用long long根本装不下。为什么会叫“智斗”因为两个阵营不是同时落子而是最后结算整张棋盘的归属。我们只关心最终状态不关心过程。这种问题本质上是一个计数问题给定约束统计所有满足条件的 0/1 矩阵数量。我第一次看到题目的时候脑子里冒出来的就是“枚举”。反正每个格子横竖只有两种选择把所有2^(N×M)种棋盘都生成出来再逐个检查对角线合法性完事。真正动手写的时候才发现如果 N×M 稍微大一点这个“完事”就是“出事”。1.2 为什么说“无脑列举”是个陷阱“无脑列举”四个字听起来很解气但实际是状态爆炸的开端。假设棋盘是 5×5一共 25 个格子总状态数是 2^25 33,554,432。三千多万个状态配合一次性生成和逐条对角线检查在 C 里勉强能跑但已经能感觉到卡顿。如果是 6×6格子数 36状态数变成 2^36约 687 亿。全球人口 80 亿每个人分到的好好数一遍都数不完更别说程序还要对每个状态做复杂的对角线检查。这就是“吓哭全世界80亿人”的由来。关键问题在于状态空间是指数增长的每多一个格子状态数直接翻倍。小数据能靠暴力蒙混过关一旦数据规模超过某个临界点就连超级计算机也救不了。所以这种题目真正想考察的并不是“你会不会枚举”而是“你知不知道什么时候不能枚举以及如何让枚举变得有重点”。2. 无脑列举为什么被吓哭复杂度账本2.1 第一版暴力枚举的思路为了验证题意我第一次写的就是最粗暴的全枚举用一个整数 mask 表示整张棋盘mask 的二进制位从第 0 位到第 N×M-1 位分别对应按行优先顺序排列的格子0 代表光阵营1 代表暗阵营。然后从 0 循环到(1 (N*M)) - 1对每个 mask 提取出棋盘数组再检查所有对角线上是否存在连续 K 个同色。检查函数也不需要什么高级技巧把每条对角线上的格子收集到一个数组里然后对数组做一次滑动窗口看有没有长度 K 且所有值相同的窗口。代码写出来挺长但逻辑很简单bool hasK(const vectorint line) { if ((int)line.size() K) return false; int cnt 1; for (int i 1; i (int)line.size(); i) { if (line[i] line[i - 1]) cnt; else cnt 1; if (cnt K) return true; } return false; } bool judge(int mask) { for (int i 0; i N * M; i) { board[i / M][i % M] (mask i) 1; } // 遍历所有主对角线从第一行或第一列作为起点方向右下 for (int sx 0; sx N; sx) { for (int sy 0; sy M; sy) { vectorint line; int x sx, y sy; while (x N y M) { line.push_back(board[x][y]); x; y; } if (hasK(line)) return false; vectorint line2; x sx; y sy; while (x 0 y M) { line2.push_back(board[x][y]); x--; y; } if (hasK(line2)) return false; } } return true; }注意这里为了省事从每个格子都当了一次对角线起点所以会重复遍历很多条对角线正确性没问题性能只是更差。真正比赛里肯定不能这么写但用来验证小数据完全够用。跑 N4M4K3 的时候32 个格子2^1665536 个状态一秒钟出结果成就感满满。然后我把测试数据改成 N5M5程序就开始转圈了等了几分钟没出结果。那一刻我才意识到这题根本没打算让你无脑列举。2.2 算了算账状态数到底有多可怕要知道 2^25 是三千多万这个数字对一个普通 C 循环来说其实没有那么可怕一分钟内跑完是有可能的。但问题是每个状态还要做对角线检查每次都涉及对 25 个格子的拆位填充以及对几十条对角线的滑动扫描总操作量轻松上亿。再加上递归或者循环本身的开销五分钟都不一定跑得完。如果继续加数据比如 N6M62^36 个状态就算一个状态只花一纳秒也要 6870 多秒大概一百多分钟。如果 K 很小剪枝几乎不起作用那这题可以直接放弃了。我在本地试着跑了一下 7×7 的棋盘程序启动以后风扇直接起飞内存占用虽然不高但时间完全不可控。那会儿我才真正理解“指数爆炸”这个词每多一个格子工作量翻倍这不是线性增长也不是平方增长而是纯粹的指数增长。80 亿人口每人分配一个状态都要分不完全世界加起来的算力也扛不住这种枚举。所以“无脑列举”不是一个技术方案而是一个数据库提示这道题需要把剪枝和状态搜索结合起来把不可能的分支尽可能提前砍掉。3. 从“无脑”到“带脑子”回溯剪枝实战3.1 边填边查让非法方案早死早超生正确的做法不是先生成完整棋盘再检查而是用 DFS 一个格子一个格子地填颜色每填完一个格子立刻检查这个新格子有没有在某个对角线上造成“连续 K 个同色”。如果已经造成了说明从这个分支往下无论怎么填都不可能变合法直接剪掉。为什么可以这样剪因为棋盘上新增的每一种颜色只会影响包含当前格子的那些对角线。只要以当前格子为终点或者中间点延伸出去的同色连续段长度小于 K那么当前状态下就没有非法点。等下一个格子填下去再检查下一个点即可。这样就能把暴力枚举里的大量无效状态提前排除。比如 K3某条主对角线上已经有了两个连续的 1现在又准备把一个 1 填在它们后面check 的时候立刻发现连续长度到了 3于是这个分支直接返回。省下的不只是这一个状态而是以这个非法状态为根的一整棵子树节省量非常可观。3.2 关键代码check 函数和 DFS 主流程核心检查函数如下。当前格子坐标为 (x,y)颜色为 cur我们只需要沿两条对角线、各自两个方向延伸统计连续同色长度bool check(int x, int y) { bool cur board[x][y]; // 主对角线方向从左上到右下 int len 1; for (int i 1; i K; i) { int nx x - i, ny y - i; if (nx 0 || ny 0 || board[nx][ny] ! cur) break; len; } for (int i 1; i K; i) { int nx x i, ny y i; if (nx N || ny M || board[nx][ny] ! cur) break; len; } if (len K) return false; // 副对角线方向从右上到左下 len 1; for (int i 1; i K; i) { int nx x i, ny y - i; if (nx N || ny 0 || board[nx][ny] ! cur) break; len; } for (int i 1; i K; i) { int nx x - i, ny y i; if (nx 0 || ny M || board[nx][ny] ! cur) break; len; } return len K; }这里有个细节len 初始值设为 1就是当前格子自己。从左侧和右侧分别延伸最后 len 表示包含当前格子的、在该对角线方向上的全部连续同色长度。只要 len K说明出现了非法段立即返回 false。DFS 主流程也简单用idx表示当前要填第几个格子从 0 到 N×M-1void dfs(int idx) { if (idx N * M) { ans; if (ans MOD) ans - MOD; return; } int x idx / M; int y idx % M; board[x][y] 0; if (check(x, y)) dfs(idx 1); board[x][y] 1; if (check(x, y)) dfs(idx 1); }主函数里输入 N、M、K调用dfs(0)最后输出ans % MOD就行。这里的 ans 用long long保存防止中途累加溢出最后取模。跑 5×5 的数据剪枝后的效率比暴力枚举高了一个数量级。K 越小剪枝越弱K 越大剪枝越强。K2 意味着任何对角线上都不能有两个同色相邻这几乎强制要求每条对角线上的颜色必须交替剪枝会非常猛状态数断崖式下降。3.3 一个小优化枚举顺序对剪枝的影响DFS 的填格子顺序居然会影响运行时间这是我一开始没想到的。按idx x*M y从上到下、从左到右填是比较自然的顺序。但棋盘的对角线限制是倾斜的如果你先填左上角再填右上角中间需要跨过好几行才能形成一条完整对角线早期很难触发剪枝。我测试过改成按“主对角线顺序”填也就是先填 (0,0)再填 (0,1)、(1,0)、(0,2)、(1,1)、(2,0)……这样能更早建立斜向相邻关系剪枝触发更早运行时间能缩短约 30%。代价是实现稍微绕一点需要预先算好每个格子的填充顺序。对这种小棋盘搜索题排序优化值得一试。4. 填坑记录那些让 AC 变难的错误4.1 超时不是唯一的问题答案错误更搞心态我第一次把回溯代码写完后小数据跑得好好的换一组数据就开始输出错误答案。排查了半天发现 check 函数里我漏了考虑当前格子往两个方向延伸时两个方向可能同时有同色段合并起来超过 K。当时只检查了一个方向导致右边已经有 2 个同色、左边又有 2 个同色时没被判非法。修正成两个方向累计长度后问题才解决。还有一个容易翻车的地方board是全局数组DFS 回溯恢复现场没做好。虽然填充过程中每个格子都会被重新赋值但如果你在递归返回后希望保留某种状态就必须显式恢复。我在这份代码里没有恢复因为下一个分支马上会覆盖但一旦你在 check 之外还要依赖历史数据就很容易出错。建议养成习惯递归前赋值递归后恢复避免未来改动时踩坑。4.2 位运算的优先级和溢出坑如果继续用 mask 做优化比如用整型参数传递棋盘状态一定要小心位运算的优先级。mask (1 i) ! 0这种写法会先算(1 i) ! 0然后mask 1结果完全不是你想要的。正确写法是(mask (1 i)) ! 0。这种细节编译器不会报错只会给你一个神秘的数字。溢出也要注意。N×M 超过 30 时1 (N*M)里如果直接写1 40在普通 32 位整型上会崩因为1是 int移位超过 31 属于未定义行为。要么用1LL (N*M)要么干脆放弃枚举改用回溯。我见过有人因为这个问题调了一晚上最后发现所有状态都是错的。4.3 取模别乱取MOD 只在累加时做答案需要对 1e97 取模但这并不代表 check 函数里的长度判断也要取模。为了保证剪枝正确所有棋盘颜色、连续长度都必须用原始值。如果你在 DFS 传入的某个参数上顺手% MODK 的比较就会变得莫名其妙。我一开始把 ans 取模放在每次递归前结果小数据没事大数据少了很多就是因为对局部参数取模破坏了状态一致性。正确做法是 ans 只在累加时取模棋盘和长度保持原样。格式上可以用ans (ans 1) % MOD但更快的写法是ans; if (ans MOD) ans - MOD;因为每次只会加 1ans 又一直保持小于 MOD所以一次 if 就够了。4.4 栈溢出和多余打印递归深度最大是 N×M正常也就 20 左右栈溢出基本不可能。但如果有人把棋盘的维度写成 100然后自己乱剪枝DFS 深度上千也危险。这种题目数据范围通常克制不用太担心。倒是调试时不要随手printf每个状态一旦输出成百上千行程序会慢到像死循环还会干扰你看结果。我通常会在调试时加一个全局变量统计合法状态数最后对比输出。5. 从这道题总结的枚举题通用套路5.1 先算状态空间再决定算法拿到任何需要“列举所有情况”的题目第一件事不是写代码而是算规模。如果总状态数量在千万级暴力枚举可能还能接受如果上了亿就一定要考虑剪枝、状态压缩或者数学推导。不用怕算错只要数量级对就能指导方向。这道题的状态数是 2^(N×M)你看到指数就知道不能蛮干。更准确地说你还要估算“单次判断的代价”。之前暴力枚举要生成棋盘再检查对角线单次判断代价几十次操作回溯剪枝单步判断也是几十次操作但搜索空间远小于 2^(N×M)。所以关键不是循环写得多漂亮而是能不能尽早砍掉大部分分支。5.2 剪枝的核心找到“最早产生冲突”的时刻回溯剪枝的本质就是让非法状态尽早暴露。对这类染色问题一个格子一个格子填每填一个就检查局部冲突是标准的套路。难点在于 check 函数要覆盖所有约束且不能漏掉跨越多步才形成的连续段。我后来总结经验剪枝检查不要只考虑当前格子本身要考虑“当前格子加入后哪些以它为端点或经过它的线段可能形成非法段”。把所有可能方向列全然后逐一检查。宁可多检查几次也不要漏查。5.3 能公式化的部分千万别硬搜如果题目限制特别强比如 K2你会发现很多方案会被强制成黑白交替此时可以用递推或者组合数学直接算。可惜这道题限制的是对角线递推公式不好写不然我也想去试试。但这也提醒我们枚举只是保底手段真正的进阶是观察约束能不能转化成更简单的等价条件。遇到这类题先手动列几个小棋盘的数据比如 2×2、3×3看有没有规律。如果没有再回头安心写搜索。5.4 最后聊点实在的这道题让我重新认识了“无脑列举”的边界。以前写题总喜欢用最直白的思路去蒙数据觉得暴力也能过现在我会先在草稿纸上画一画状态树算一下最坏情况分支数。真正常见的不是算法不会写而是明明预估到会超时还安慰自己“优化一下循环就能过”。如果让我给新手一个建议遇到排列组合型计数题先把暴力版本写出来用小数据验证正确性再逐步加剪枝。这个顺序能帮你少走很多弯路。直接上高级优化而没有一个正确暴力版本做对照出错时你根本不知道是思路错了还是细节写错了。这道智斗题我现在还记得很清楚。它没什么高级数据结构没有线段树也没有复杂图论就是把回溯、剪枝、位运算和复杂度估算这些基本功揉在一起。很多时候决定一道题能不能 AC 的不是你会多少奇技淫巧而是面对指数爆炸时你愿不愿意静下心来把搜索树砍得足够细。下次再看到有人鼓吹“无脑列举”我大概会笑一笑年轻人你的电脑风扇还在转呢。