蓝桥杯必考：深度优先搜索与回溯剪枝解题模板（含全国青少年信息素养大赛、电子学会 C/C++ 考级对照）-育师

蓝桥杯（第 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`描述「走到哪了、踩过哪些格子」
选择枚举	四个方向依次尝试，相当于状态树的四条分支
约束判断（剪枝）	越界 / 踩到障碍 / 格子已访问 → 直接放弃该分支
回溯与撤销	进入分支前标记`vis=true`，递归返回后`vis=false`还原，让兄弟分支能复用格子
终止条件	到达 (R,C) 时计数 +1 并`return`
复杂度意识	最坏是指数级，必须靠剪枝或约束规模来收敛

三、解法 / 拆解

3.1 朴素 DFS 回溯（四方向不重复，枚举计数）

思路一句话：递归往下走，能走就标记，走不通或走完了就撤销标记回去试别的路。

C++ 版本

#include <iostream> #include <vector> using namespace std; int R, C; vector<vector<int>> blocked; // 1 表示花坛/水池，不能走 vector<vector<bool>> 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, vector<int>(C + 1, 0)); vis.assign(R + 1, vector<bool>(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；中心障碍输出 2

3.2 时间与空间复杂度

时间：最坏情况下每个格子有 4 个方向、且大多能走，状态树规模接近O(4^(R*C))。3×3 无障碍有 12 条路径尚可，4×4 无障碍已达 184 条，更大网格会指数爆炸——这正是搜索题必须用剪枝或限制规模的原因。
空间：递归深度最坏R*C，visited占用O(R*C)，整体空间O(R*C)。

3.3 六易错点（考场高频丢分）

忘记回溯撤销：只vis=true不vis=false，兄弟分支看不到这个格子，答案必然偏小甚至为 0。
起点没标记访问：从 (1,1) 出发前要先vis[1][1]=true，否则可能第一步又走回起点形成环。
坐标越界写成0<=nx：题目是 1 基坐标，应是1<=nx<=R。
答案类型用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; vector<vector<int>> blocked; vector<vector<long 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, vector<int>(C + 1, 0)); memo.assign(R + 1, vector<long 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，蓝桥杯「路径之谜」常用此招。
双向 DFS（Meet in the Middle）：从起点和终点同时出发，在中间相遇。搜索深度减半，能扛更大网格。
状态压缩记忆化：当网格较小（如 ≤ 10×10），把visited压成整数位掩码，连同坐标(x,y)组成状态key，用哈希表记忆化。这是「记忆化搜索」与「动态规划」的桥梁：重复状态直接返回结果。
与 DP 的关系：「只允许右/下」是 DAG 上的计数 DP；「四方向不重复」因有环、状态依赖历史路径，只能靠回溯枚举或状态压缩 DP。理解这点，就能在考场上判断「这题该写搜还是写 DP」。
蓝桥杯「路径之谜」思路：在回溯里同时维护「每行 / 每列已踩格子数」，与目标计数表比对，不满足立即剪枝，能瞬间砍掉大量无效分支。