1. 这套题单为什么值得刷“kuangbin带你飞”这个名字在算法竞赛圈子里流传了很多年尤其是专题一“简单搜索”几乎是每一位入门选手都会接触到的第一套完整刷题清单。很多刷题指南、经验帖、训练营都把它作为起点不是因为它简单而是因为它把“搜索”这个看似只可意会不可言传的算法概念用一组题目拆解得明明白白。先讲个背景。当年刚开始接触算法竞赛时我也经历过“看懂了DFS和BFS的讲解但拿到题目完全不知道从哪里下手”的尴尬期。课本上讲递归、讲队列、讲回溯例题也看得懂但一换题目就懵。这种情况在初学者里非常普遍根本原因在于搜索类题目看起来都是一个套路实则每个题目的状态定义、判重方法、剪枝策略都不一样没有大量题目喂进去很难建立起解题直觉。而这套专题的定位就是专门用来解决这个问题的。专题一共几十道题核心覆盖两大类方法深度优先搜索DFS和广度优先搜索BFS同时穿插了回溯、状态压缩、连通块、最短路变体等经典模型。它解决的痛点是让你在短期内集中、密集地接触搜索题的多种变式把“会写模板”变成“会做题目”。适合的人群非常明确——刚学完基础语法、懂递归但没刷过几道题的新手也适合学过一段时间、想系统梳理搜索题型的选手。这套题单之所以长盛不衰我觉得有两个关键原因。一是题目质量确实高题目之间没有滥竽充数的凑数题每道题都在某个细节上有讲究刷完顺便把DFS和BFS的边界情况、常见坑摸了个遍。二是它的组织方式合理不是按题目难度线性排列而是按类型排列前几道先让你把“棋盘问题”“连通块问题”这类入门题做熟后面再逐步追加难度引入状态压缩和剪枝较深的内容。这种编排方式意味着你可以按顺序一路刷下去每一步踩的坑都会在后面的题目里用得上。另外这套题单虽然叫“简单搜索”但实际上覆盖的模型并不浅。拿后面的题目来说有的要处理多源BFS、有的涉及二进制的状态压缩、有的需要在搜索过程中维护复杂的状态这些都是更高阶算法的基础。把这一专题吃透去打其它判题网站的搜索题基本不会再有“看不懂题解”的情况。2. 搜索问题的整体思路拆解2.1 搜索的本质把选择变成状态搜索类问题说白了就是在做一件事把题目里的所有可能情况组织成一个可以遍历的结构然后按照某种顺序去遍历它。这个结构通常是一棵隐式的树或图每个节点代表一个状态节点之间的边代表一次操作或一步移动。DFS对应的是沿着一条分支走到底走不动了再掉头BFS对应的是按层推进一层一层往外扩散。这个思想用生活场景来类比就很直观。假设你在一栋陌生的楼里找一个人DFS的做法是随便挑一个方向一直走遇到岔路先记住走到死胡同就退回来走另一条BFS的做法是先把当前楼层的每个房间都看一遍没人再去下一层。前者代码写起来短后者能保证找到最短路线。理解了这层关系再看题单里的题目就清晰了每道题本质上都是在问“这棵树怎么建”“用哪种方式走更合适”。以专题一里的题目为例棋盘类问题是典型的DFS场景因为每一步放置的位置会影响到后续的选择连通块类问题两种方法都行因为只关心“能不能到”而不关心“怎么到最省”迷宫最短路则必须用BFS因为要保证第一次到达时路径最短。2.2 为什么DFS和BFS各有适用场景这是初学搜索时最容易糊涂的地方也是专题一反复在考察的点。分清楚什么时候用哪个方法比背模板重要得多。DFS的核心特征是“一条路走到黑”。它适合解决的问题有三大类是否存在某个解比如是否存在一条路径所有解的列举比如全排列、组合需要在搜索过程中逐步构建答案的场景比如棋盘放入问题、数独类问题DFS的实现依赖递归或手动栈代码结构一般较短但需要注意回溯。回溯的意思是当递归返回到上一层时要把之前修改过的状态恢复原样否则后续分支的搜索会受到污染。BFS的核心特征是“层层推进”。它最适合解决的问题是最短路径在无权图上BFS第一次到达某个状态时的步数一定是最短的最少步数、最少操作次数多源扩散类问题多个起点同时向外扩BFS的实现依赖队列每个节点出队时向四周扩展需要判重防止重复入队。只要每个状态只入队一次时间复杂度就是可控的。值得一提的是有些题目两种方法都可以用只是答案的表现形式不同。比如连通块计数DFS和BFS都能做只是DFS的代码更短而最短路类题目则基本锁死BFS因为DFS不能保证第一次搜到的路径最短。2.3 状态定义与判重搜索题的核心难点很多时候搜不出来或者超时问题不在遍历顺序而在状态定义和判重设计。状态指的是在搜索过程中需要记录的全部信息。比如迷宫问题状态就是坐标x, y棋盘放入问题状态是“已经放了k个棋子的棋盘”如果题目里有两个物品同时移动状态就要同时包含两个位置。状态定义得准不准确直接决定搜索能不能往正确的方向推进。判重则是避免重复访问同一个状态。如果完全没有判重搜索空间会爆炸很多题目甚至跑到机器内存耗尽都跑不完。判重的常见手段包括一维数组标记已访问坐标二维数组标记棋盘状态布尔数组标记“某一步数下是否到达过某个状态”二进制状态压缩配合数组或哈希表标记状态专题一里有一个特点几乎每道题都需要判重但每道题的判重方式又不完全一样。刷题时会发现在最简单的题目里用visited[][]就够了而有一些题要把整张棋盘的状态压缩成一个整数来判重。这种设计就是故意让你慢慢适应“状态在变复杂判重要跟着升级”的节奏。3. 核心算法框架与代码模板3.1 DFS的递归模板与回溯技巧DFS的代码框架非常固定但细节决定成败。给一个常见的回溯型DFS模板void dfs(int step) { if (step target) { // 到达终态判断是否满足题目要求 // 记录答案或更新最优值 return; } for (int i 0; i choices; i) { // 枚举当前层的所有可能选择 if (可行) { 标记状态 // 做选择 dfs(step 1); // 递归进入下一层 恢复状态 // 撤销选择回溯 } } }这里最容易被忽略的是“恢复状态”。新手经常写完递归发现输出结果不对调试半天才发现是上一层的标记没撤销导致本层本该可行的分支被跳过了。引用一个经典例子。棋盘类题目要求在N×N的棋盘上摆放棋子同一行同一列只能有一个棋子。DFS搜索时每放一个棋子就要把这一列标记为“已占用”递归返回后必须清除这个标记。如果不清除下一步搜索会认为所有列都被占了从而漏掉大量有效解。另一种DFS写法不需要回溯那是针对“状态只增不减”的情况比如标记已访问过的格子后直接递归不需要恢复因为一个格子访问过了就不再需要访问。这个区别需要根据题目语义判断不能死套模板。3.2 BFS的队列模板与层数控制BFS的模板相对更机械一些但有几个容易踩坑的点queueNode q; q.push(start); vis[start] true; while (!q.empty()) { Node cur q.front(); q.pop(); // 处理当前节点 if (cur target) { // 记录答案 break; } for (int i 0; i 4; i) { // 上下左右四个方向 int nx cur.x dx[i]; int ny cur.y dy[i]; if (边界合法 !vis[nx][ny]) { vis[nx][ny] true; // 入队前标记防止重复入队 q.push({nx, ny}); } } }注意这里的“入队前标记”是一个重要细节。很多初学写法是出队时再标记这样会导致同一个节点被多次加入队列不仅浪费内存还可能让搜索陷入死循环。正确做法是入队的同时立刻标记。另一个常见问题是怎么记录步数。推荐的做法是在节点结构体里直接带上step字段每次扩展时step加1或者使用分层BFS每次while循环开始时先记录当前队列的大小处理完这批再进入下一层。前者好理解后者节省一点内存实际用起来差别不大。3.3 方向数组与边界处理方向数组是搜索题里一个不起眼但非常重要的工具。对于二维网格上的搜索通常定义int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};分别对应上、下、左、右四个方向。有些八方向题目会扩展成8个方向包括四个斜角。方向数组本身没有难度但容易在边界条件上写错。常见错误是数组越界在Java或C中越界访问不会直接报错而是读取到未知内存导致程序行为异常调试起来非常难受。最保险的边界处理方式有两种。一种是每次扩展时判断是否在0到n-1、0到m-1范围内另一种是在地图四周加一圈障碍物边界让所有访问都在合法范围内。前者更直观后者代码写起来更省事实际做题时可以根据题目情况选择。对于字符串读入的地图还要注意换行符的问题。有些题目用scanf或cin读入字符矩阵时行末的换行符会被当作一个字符读走导致地图错位。正确的做法是每行用字符串整体读入再逐字符处理或者使用getchar()把多余换行吞掉。4. 专题一中的典型题目逐类拆解4.1 棋盘类问题DFS回溯的入门试金石专题一的前几道题几乎都在围绕棋盘做文章。这类题的共同点是有一个棋盘或矩阵需要放置若干件物品每件物品放置时受到某些约束要求统计方案总数或找到可行解。以经典的棋盘放入问题为例题目大意是在N×N的棋盘上放置k个棋子棋盘有些位置可以放标记为‘#’有些位置不可以放标记为‘.’并且任意两个棋子不能在同一行或同一列。问有多少种不同的放置方案。解题思路是非常标准的DFS回溯。把“当前搜索到第几行”和“已经放置了几个棋子”作为递归参数。在每一行可以选择不放棋子直接进入下一行也可以尝试在当前行每个可放位置放一个棋子同时标记该列已被占用。递归终止条件是放完了k个棋子此时计数加一。这个题的坑在“这一行可以不选”。新手很容易把代码写成“每一行必须放一个”漏掉跳行的情况导致结果偏小。另外搜索过程中需要传递当前行号而不是从头开始枚举否则会产生重复计数。具体的核心代码如下void dfs(int row, int cnt) { if (cnt k) { ans; return; } if (row n) return; // 当前行不放棋子 dfs(row 1, cnt); // 当前行尝试放棋子 for (int col 0; col n; col) { if (map[row][col] # !used[col]) { used[col] true; dfs(row 1, cnt 1); used[col] false; } } }这段代码的精髓是“当前行不放棋子”和“放棋子”两条路径都要走而且必须走完整张地图的所有行才能保证所有方案都被枚举到。这个模板可以迁移到很多类似的棋盘约束问题中去。4.2 连通块类问题理解DFS与BFS的边界连通块问题在专题一中也占了不少份额。这类题判断一个区域内有几片相连的陆地区域或者统计某个区域内格子的数量。题目描述往往长得很吓人但模型非常统一把整个地图扫一遍遇到一个未访问的合法格子就采用DFS或BFS把整块区域标记完计数器加一。以某个油田探测问题为例地图由“”和“*”组成要求统计相邻的“”构成的连通块数量。这里的相邻指8个方向也就是上下左右加四个斜角。解题时双重循环遍历地图一旦遇到未被访问的“”就从这里开始DFS把周围所有连通的“”都标记掉。每次DFS进去之后把当前格子标记为已访问然后检查周围8个方向。这里方向数组的长度要改成8否则漏了斜方向的连通答案会偏小。有些题目把这种情况描述成“八个方向均视为相邻”一定要仔细读题不能默认只有上下左右。DFS版本的连通块代码可以做得很简洁一个函数递归调用自己BFS版本则多一个队列。实际刷题时连通块问题用DFS写起来更顺手代码量更小。但如果在极其稠密的网格上搜索DFS递归深度可能非常大极端情况下会造成栈溢出这时改用BFS或者显式栈会更稳妥。4.3 迷宫最短路BFS能保证最短的依据迷宫类题目是专题一里最“像游戏”的一类。输入一张地图包含起点和终点有些格子能走有些不能走求从起点到终点的最短步数。这里有个关键点如果地图上每一步的代价都相同都是1那么BFS第一次扩展到终点时得到的步数一定是最短的。原因是BFS在队列中按距离分层扩展距离为1的所有节点会被先处理完然后才是距离为2的节点以此类推。所以当终点第一次被出队时它的距离就是所有可行路径中的最小值。DFS没法保证这一点因为DFS一旦走了一条较长的路径先到达终点如果没有额外判断就会得到一个偏大的答案。这个性质是BFS一类问题的核心依仗专题一反复用不同的迷宫变式来强化这个认知。有些题目是最少步数有些是要求输出路径有些是倒着从终点走回起点来构造路径本质都是同一套BFS模板加上了一些附加输出要求。如果在广度优先遍历的同时要求输出最短路径常见做法是在BFS过程中记录每个节点的前驱节点到达终点后回溯打印。也可以用结构体数组存储每个格子的“来源方向”到达终点时按方向反向拼接路径。4.4 状态压缩搜索专题一的天花板专题一的末尾部分会出现用二进制表示状态的高阶搜索题。一个典型的场景是一个数轴或一个序列某个操作会同时影响多个位置的状态需要求从初始状态到目标状态的最少操作次数。这类题的核心是状态压缩。把整个序列的当前状态用一个整数的二进制位表示状态总数就是2的N次方。搜索时每个节点的状态是一个整数判重用一个布尔数组来标记。BFS的队列中存的下一个状态是当前状态经过一次操作后得到的新整数。状态压缩最大的难点不是理解二进制而是如何设计状态的转移。举个例子如果一个操作可以让连续的三个位置翻转1变0、0变1那么对于当前状态status执行这次操作后新的状态就是status异或上一个对应位置的掩码。需要事先把每个操作的掩码算好BFS时直接枚举掩码进行一次异或运算。这种思路一旦跑通后面很多更复杂的搜索题比如八数码、华容道模型的简化版都能顺着这个方向理解。专题一里这类题目数量不多但放在最后非常合理因为它把“状态”这个概念从二维网格提升到了抽象整数为后续学习更高级的算法如状态压缩DP、记忆化搜索做了铺垫。5. 刷题过程中避不开的坑5.1 递归爆栈为什么有时候代码“没毛病”却崩溃不少人刷到连通块或状态压缩题时会遇到程序运行到一半直接退出或者报“段错误”。一个很大的嫌疑是递归层数太深超过了系统栈的限制。这里分享一个直观的估算方法。C默认的栈空间一般在几MB级别一次递归调用本身占用的栈帧不大但如果递归深度达到数万层就很容易爆栈。二维网格类题目如果地图尺寸很大用DFS一条路走到底极端情况下可能会访问整张网格的所有格子递归深度就是网格大小。应对方法有三个方向改用BFS用队列替代递归调用不占用系统递归栈手动模拟递归用显式栈存储待搜索的状态在允许的环境中增大栈空间配置实际刷题时如果题目地图尺寸较大且搜索空间接近满铺我一般优先考虑BFS代码结构也更直观。5.2 判重标志的位置一个字符的错误前面提到BFS要在入队时标记这里再强调一次。新手经常写成“出队时标记”看似差不多实际后果很严重。出队时标记会让同一个状态被多次加入队列因为它在入队时没有被标记后续扩展可能再次生成它。处理小规模数据时可能看不出问题一旦状态量增大队列膨胀速度会非常可观。DFS回溯的恢复操作也是容易出错的地方。如果一道题里某个标志在递归调用前被修改必须在递归返回后立刻恢复否则会影响兄弟分支的搜索。这里有一个调试经验如果发现方案数偏少优先怀疑是某个标志没有恢复如果发现方案数偏多优先怀疑是某个非法状态没有被拦截。5.3 输入地图的读入坑字符矩阵的读入是搜索题里让很多人抓狂的一类细节。用C风格读字符时换行符很容易被误读成地图内容导致整体错位。我自己的习惯是无论什么语言一律按行读字符串然后逐字符放入地图数组。这样可以最大程度避免换行符问题。对于Java选手建议用BufferedReader按行读对于C选手建议用cin直接读string类型或者用getline。按字符读入的写法不是不行但每次都要处理多余的换行心智负担比较大。5.4 时间和内存的预判搜索题看上去没有复杂算法但数据范围大起来照样能让你超时。做搜索题之前先扫一眼数据范围判断DFS直接搜会不会超时。记住一个经验BFS的状态总数如果控制在百万级别以下一般都能在1秒内跑完如果状态空间达到千万级就要小心常数优化了。常见的优化思路有调整方向顺序优先搜索更可能通向答案的分支提前剪枝在递归入口判断当前状态是否还有可能达到目标使用位运算代替数组操作压缩状态加入启发式排序让搜索顺序更合理但这里要提醒一句专题一里的大部分题目范围设计得比较克制不需要过度优化也能通过。真正需要优化时题目会明确暗示数据范围较大。不要在入门阶段就沉迷于花里胡哨的剪枝先保证思路正确、代码清晰再逐步考虑效率问题。6. 如何按顺序刷完这一专题6.1 推荐的刷题节奏专题一虽然叫“简单搜索”但对小白来说体量并不小。我的建议是不要贪快按类型分阶段刷完每一阶段做完认真总结。第一阶段棋盘类问题。先把DFS回溯的模板练熟做到不看模板也能写出来。这一阶段的题目解答过程几乎一样核心目的是形成肌肉记忆。第二阶段连通块类问题。练习DFS和BFS两种写法对比两种方法的代码差异。建议同一道题用两种方法各写一遍理解各自的适用场景。第三阶段迷宫最短路问题。集中练习BFS重点掌握步数记录和路径输出。第四阶段状态压缩与较复杂的搜索问题。这一阶段比较吃力可以先看题解里的状态定义思路然后再自己独立写一遍。每个阶段结束之后建议把自己写过的代码重新看一遍对照错误记录总结易错点。这个环节的作用不是复述代码而是逼自己回忆当时的思考过程。6.2 如何高效看题解刷题过程中卡住很正常但看题解的方式有讲究。不建议一卡住就立刻看题解那样学不到东西。我自己习惯的流程是先自己思考至少20分钟明确卡在哪个环节如果是状态定义不清楚先看题解的“思路分析”部分不看代码想通之后自己动手写写不出来再对照代码对照完代码之后把代码关掉再独立写一遍第三步和第四步的区别在于前者知道了解题路径但不一定内化成自己的思考方式后者是在核心思路明确的情况下强迫自己完成代码层面的实现细节。还有一个比较有效的方法是把同一道题隔两三天再重写一遍。第一遍写完隔几天就忘了细节重写时才算真正掌握。6.3 配套练习如何举一反三专题一本身是一个完整的训练闭环但刷完之后还应该做拓展练习。可以找其它在线评测平台的搜索标签题目选择3到5道与专题一题型类似的题目测试自己能否迁移方法。迁移练习时特别关注两点一是状态定义的变化二是判重策略的变化。比如专题一里状态可能是坐标换一道题状态可能变成钥匙的收集状态、火势的扩散时间等。每次遇到新状态都要思考“这个信息能不能用二维数组记录”“需不需要用位压缩”。建议每次刷题后做一个小结把题目考察的知识点、自己犯的错、解决方法记下来。不要小看这个习惯等刷完整个专题回头翻看会发现很多规律性内容比零散刷题要高效得多。7. 我刷完这套题之后的体会很多人问我专题一刷完到底能学到什么。这个问题我用一次实际体验来回答。在我刷这套题的最后一个阶段遇到一道题地图上包含多个目标点一次操作可以改变多个位置的状态。换作以前我大概率会卡在“这题跟迷宫有什么关系”这个想法上但经过专题一的训练后我很快就反应过来要把整张地图的当前状态编码成一个整数然后跑BFS。那一刻才真正体会到所谓“搜索”不是一道题的做法而是一种组织思路的框架。还有一个小技巧是刷题过程中摸索出来的。如果DFS和BFS都能用的题目我会惯例性地思考一下数据范围。如果数据范围很大我倾向于BFS因为循环比递归稳定如果范围较小我就选代码量更短的DFS。这个习惯后来在竞赛中帮我避免了不少反面案例。最后再说一句关于调试的体会。搜索题的错误往往不是逻辑层面的而是类似于“这个状态到底有没有被正确标记”这类细节问题。我的做法是写一个简单的输出函数在关键步骤打印当前状态和队列内容。虽然这样有点原始但定位问题的效率比反复读代码高很多。专题一的价值不在于它有多少难题而在于它用几十道题把搜索的常见模型完整地铺开了一遍。认真刷完把每一道题都弄懂后续再看其它算法专题会发现很多思想都能从这里找到源头。