蓝桥杯第 17 届省赛、全国青少年信息素养大赛算法应用赛项、以及中国电子学会 C/C 与 Python 考级这三场赛事的考点大纲里有一个共同的高频词——深度优先搜索DFS与回溯剪枝。据历年蓝桥杯省赛复盘80% 的省赛题目由约 20% 的高频算法覆盖而DFS / BFS 稳居榜首信息素养大赛的 C / Python 算法应用赛项大纲也明确把「DFS、BFS、枚举、递归、分治」列为必考电子学会考级则从三级起反复考查「递归 搜索」。换句话说吃透回溯剪枝等于同时拿下了三场赛事的入门与中档分数。本文用一道原创题「校园方格探险」带你完整走一遍状态定义 → 选择枚举 → 约束剪枝 → 回溯撤销 → 复杂度与易错点 → 与动态规划的关系并给出 C / Python 双版本。一、题目 / 项目目标校园方格探险【题目描述】校园里有一张 R 行 C 列的方格地图左上角 (1,1) 是校门右下角 (R,C) 是科技楼。某些格子是花坛或水池用1标记不能踩。小向导从校门出发每次可以向上、下、左、右四个方向走到一个尚未经过的格子最终要走到科技楼。问一共有多少条「每个格子最多只经过一次」的合法路线输入示例R 3, C 3无障碍。输出示例12从 (1,1) 到 (3,3) 的不重复简单路径共 12 条。进阶约束若把中心格子 (2,2) 设为障碍答案变为2。这道题的本质是「在状态空间里系统地枚举所有可行方案并计数」是蓝桥杯「路径之谜」「方格填数」一类题的母题。二、核心考点拆解考点说明状态定义用当前坐标(x, y) 已访问集合visited描述「走到哪了、踩过哪些格子」选择枚举四个方向依次尝试相当于状态树的四条分支约束判断剪枝越界 / 踩到障碍 / 格子已访问 → 直接放弃该分支回溯与撤销进入分支前标记vistrue递归返回后visfalse还原让兄弟分支能复用格子终止条件到达 (R,C) 时计数 1 并return复杂度意识最坏是指数级必须靠剪枝或约束规模来收敛三、解法 / 拆解3.1 朴素 DFS 回溯四方向不重复枚举计数思路一句话递归往下走能走就标记走不通或走完了就撤销标记回去试别的路。C 版本#include iostream #include vector using namespace std; int R, C; vectorvectorint blocked; // 1 表示花坛/水池不能走 vectorvectorbool vis; // 当前路径已访问标记 long long ans 0; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; void dfs(int x, int y) { if (x R y C) { // 到达科技楼计一条路线 ans; return; } for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (nx 1 nx R ny 1 ny C !blocked[nx][ny] !vis[nx][ny]) { vis[nx][ny] true; // 做出选择 dfs(nx, ny); vis[nx][ny] false; // 回溯撤销关键 } } } int main() { R 3; C 3; blocked.assign(R 1, vectorint(C 1, 0)); vis.assign(R 1, vectorbool(C 1, false)); // blocked[2][2] 1; // 若中心为障碍取消注释即可 vis[1][1] true; dfs(1, 1); cout ans endl; // 无障碍输出 12中心障碍输出 2 return 0; }Python 版本R, C 3, 3 blocked set() # 无障碍障碍示例{(2, 2)} visited set() ans 0 dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(x, y): global ans if (x, y) (R, C): ans 1 return for dx, dy in dirs: nx, ny x dx, y dy if 1 nx R and 1 ny C \ and (nx, ny) not in blocked and (nx, ny) not in visited: visited.add((nx, ny)) # 做出选择 dfs(nx, ny) visited.discard((nx, ny)) # 回溯撤销 visited.add((1, 1)) dfs(1, 1) print(ans) # 无障碍输出 12中心障碍输出 23.2 时间与空间复杂度时间最坏情况下每个格子有 4 个方向、且大多能走状态树规模接近O(4^(R*C))。3×3 无障碍有 12 条路径尚可4×4 无障碍已达 184 条更大网格会指数爆炸——这正是搜索题必须用剪枝或限制规模的原因。空间递归深度最坏R*Cvisited占用O(R*C)整体空间O(R*C)。3.3 六易错点考场高频丢分忘记回溯撤销只vistrue不visfalse兄弟分支看不到这个格子答案必然偏小甚至为 0。起点没标记访问从 (1,1) 出发前要先vis[1][1]true否则可能第一步又走回起点形成环。坐标越界写成0nx题目是 1 基坐标应是1nxR。答案类型用int路径数随网格迅速变大4×4 已 184更大时超int务必long long/ Python 自动大整数。把障碍格子当可走进入分支前必须判断!blocked[nx][ny]否则会穿过花坛。死循环 / 重复计数的边界四方向允许回头靠visited排除已踩格子忘了它就会无限递归或重复走。3.4 对比只允许「右 / 下」→ 退化成记忆化搜索 / 动态规划如果规则收紧为「每步只能向右或向下」问题立刻从「指数枚举」变成「可 DP」的「不同路径数」。带障碍时同样用 DFS 框架但加上记忆化即可C 版本记忆化搜索#include iostream #include vector using namespace std; int R 3, C 3; vectorvectorint blocked; vectorvectorlong long memo; long long f(int x, int y) { if (x R || y C) return 0; if (blocked[x][y]) return 0; if (x R y C) return 1; if (memo[x][y] ! -1) return memo[x][y]; return memo[x][y] f(x 1, y) f(x, y 1); } int main() { blocked.assign(R 1, vectorint(C 1, 0)); memo.assign(R 1, vectorlong long(C 1, -1)); // blocked[2][2] 1; // 障碍示例 cout f(1, 1) endl; // 无障碍 6中心障碍 2 return 0; }Python 版本记忆化搜索from functools import lru_cache R, C 3, 3 blocked set() # 障碍示例{(2, 2)} lru_cache(None) def f(x, y): if x R or y C: return 0 if (x, y) in blocked: return 0 if (x, y) (R, C): return 1 return f(x 1, y) f(x, y 1) print(f(1, 1)) # 无障碍 6中心障碍 2同一道「网格走路」只因移动规则不同解法就从指数回溯滑向多项式 DP——这正是蓝桥杯区分基础分与压轴分的关键。四、进阶奇偶性剪枝起点到终点的曼哈顿距离是|R-1||C-1|。若要求「不重复经过格子」且必须走满某长度奇偶性矛盾的分支可提前return蓝桥杯「路径之谜」常用此招。双向 DFSMeet in the Middle从起点和终点同时出发在中间相遇。搜索深度减半能扛更大网格。状态压缩记忆化当网格较小如 ≤ 10×10把visited压成整数位掩码连同坐标(x,y)组成状态key用哈希表记忆化。这是「记忆化搜索」与「动态规划」的桥梁重复状态直接返回结果。与 DP 的关系「只允许右/下」是 DAG 上的计数 DP「四方向不重复」因有环、状态依赖历史路径只能靠回溯枚举或状态压缩 DP。理解这点就能在考场上判断「这题该写搜还是写 DP」。蓝桥杯「路径之谜」思路在回溯里同时维护「每行 / 每列已踩格子数」与目标计数表比对不满足立即剪枝能瞬间砍掉大量无效分支。五、小结与互动DFS 回溯剪枝是把现实约束翻译成代码里的「状态 选择 撤销」的过程定义清楚状态枚举每个选择用约束做剪枝递归返回时记得撤销。它是蓝桥杯省赛的送分题常客也是全国青少年信息素养大赛算法应用赛项、电子学会 C/C 与 Python 考级递归章节的核心。本期练习把 3.1 的代码改成「输出所有路径的具体走法用 U/D/L/R 表示」再试着加上「奇偶性剪枝」看速度变化。如果你在信息素养大赛或电子学会考级备考中遇到类似的搜索题欢迎在评论区贴出题目描述下期我们可以一起拆成回溯模板。点赞 收藏备考不迷路 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。