DFS周测三题题解复盘 前言 本次周测覆盖了 DFS/BFS 的五大核心模型：
题号 题目 模型 核心特征 1 P2089 烤鸡 排列型DFS 每个位置有固定选择范围 2 P1036 选数 组合型DFS 不考虑顺序，用start去重 3 Perket 子集型DFS 每个物品选/不选，两分支 4 填涂颜色 Flood Fill 连通块标记，内外判断 5 迷宫问题 BFS预处理 连通块编号，O(1)查询
第一部分：P2089 烤鸡 基本信息 项目 内容 题目编号、来源 P2089 洛谷 / 烤鸡 训练层级 B DFS基础 知识版块 DFS、排列枚举、回溯、剪枝
解题前・关键信号识别 维度 分析 目标、约束、底层结构 目标 ：10种调料，每种选1~3克，使总重量为 n，输出所有方案；约束 ：n ≤ 10000；底层结构 ：每个位置有3种选择，形成多分支搜索树。数据规模 3^10 = 59049，DFS枚举完全可行。 候选算法和依据 DFS + 回溯；依据 ：每个位置有固定选择范围，需要枚举所有方案。 复杂度预判 时间复杂度 O(3^10)，空间复杂度 O(10)。
解题后・外化复盘 维度 内容 实现结构 / 核心思路 第一步定义dfs(step, sum)，step 表示当前处理第几种调料，sum 表示当前总重量；第二步若step == 10，检查sum == n，满足则记录方案；第三步枚举 i 从 1 到 3，path[step] = i，递归dfs(step+1, sum+i)。核心思想 ：每个位置枚举所有可能取值，递归填下一个位置。 错因回溯 1. 出口忘记写return，导致继续执行；2. 剪枝不足：只判断sum > n，未考虑剩余调料的最小/最大贡献； 边界和易错点 1. 出口必须return；2. n 的范围是 [10, 30]，超出直接输出 0；3. 剪枝条件：sum + (10-step) > n和sum + (10-step)*3 < n；4. path 数组保存当前方案，递归返回后自动覆盖，无需显式回溯。 下次看到什么信号，我应该想到这个方法 看到「每个位置有多个固定选择 + 枚举所有方案 」，用排列型DFS。
AC 完整代码 # include <iostream> # include <vector> # include <string> # include <algorithm> using namespace std; int n; int path[ 10 ] ; vector< vector< int >> plans; void dfs ( int step, int sum) { if ( sum> n) return ; if ( sum+ ( 10 - step) > n) return ; if ( sum+ ( 10 - step) * 3 < n) return ; if ( step== 10 ) { if ( sum== n) { plans. push_back ( vector < int > ( path, path+ 10 ) ) ; return ; } } for ( int i= 1 ; i<= 3 ; i++ ) { path[ step] = i; dfs ( step+ 1 , sum+ i) ; } } int main ( ) { cin>> n; if ( n< 10 || n> 30 ) { cout<< 0 << endl; return 0 ; } dfs ( 0 , 0 ) ; cout<< plans. size ( ) << endl; for ( auto & p: plans) { for ( int i= 0 ; i< 10 ; i++ ) { cout<< p[ i] << " " ; } cout<< endl; } return 0 ; } 第二部分：P1036 选数 基本信息 项目 内容 题目编号、来源 P1036 洛谷 / NOIP2002 普及组 训练层级 A DFS 知识版块 DFS、组合枚举、素数判断
解题前・关键信号识别 维度 分析 目标、约束、底层结构 目标 ：从 n 个数中选 k 个，求和为素数的方案数；约束 ：n ≤ 20；底层结构 ：组合枚举（顺序无关），用 start 参数控制枚举起点。数据规模 n ≤ 20，组合数 C(20,10) = 184756，DFS 完全可行。 候选算法和依据 DFS + 回溯；依据 ：选 k 个数求和，顺序无关，属于组合枚举。 复杂度预判 时间复杂度 O(C(n,k))，空间复杂度 O(k)。
解题后・外化复盘 维度 内容 实现结构 / 核心思路 第一步读入 n, k 和数组 a；第二步定义dfs(step, start, sum)，step 表示已选了几个数，start 表示当前从哪个下标开始枚举，sum 表示当前总和；第三步若step == k，检查 sum 是否为素数，若是则 ans++；第四步枚举 i 从 start 到 n，递归dfs(step+1, i+1, sum+a[i])。核心思想 ：组合不计顺序，下一层从 i+1 开始枚举，避免重复。 错因回溯 1. 递归写成dfs(step+1, start+1, ...)而不是i+1；2. 出口忘记return； 边界和易错点 1. 组合用 start 参数，不需要 visited；2. 下一层递归传i+1，不是start+1；3. 出口必须return。 下次看到什么信号，我应该想到这个方法 看到「从 n 个数中选 k 个 + 顺序无关 + 判断条件 」，用组合DFS。
AC 完整代码 # include <iostream> using namespace std; int n, k, ans; int a[ 25 ] ; bool isPrime ( int x) { if ( x< 2 ) return false ; if ( x== 2 ) return true ; if ( x% 2 == 0 ) return false ; for ( int i= 3 ; i* i<= x; i+= 2 ) { if ( x% i== 0 ) return false ; } return true ; } void dfs ( int step, int start, int sum) { if ( step== k) { if ( isPrime ( sum) ) ans++ ; return ; } for ( int i= start; i< n; i++ ) { dfs ( step+ 1 , i+ 1 , sum+ a[ i] ) ; } } int main ( ) { cin>> n>> k; for ( int i= 0 ; i< n; i++ ) { cin>> a[ i] ; } dfs ( 0 , 0 , 0 ) ; cout<< ans<< endl; return 0 ; } 第三部分：Perket 基本信息 项目 内容 题目编号、来源 Perket 训练层级 B DFS进阶 知识版块 DFS、子集枚举、选/不选模型
解题前・关键信号识别 维度 分析 目标、约束、底层结构 目标 ：选择若干种食材，使酸度（乘积）和苦度（和）的差的绝对值最小；约束 ：每个食材只有选/不选两种状态；底层结构 ：子集枚举，每个物品两个分支。数据规模 n≤10，2^n完全可行。 候选算法和依据 DFS+回溯；依据 ：每个物品选/不选，枚举所有子集。 复杂度预判 时间复杂度O(2^n)，空间复杂度O(n)。
解题后・外化复盘 维度 内容 实现结构 / 核心思路 第一步定义dfs(step, sour, bitter, choose)，step表示当前处理第几个食材，sour表示当前酸度乘积，bitter表示当前苦度和，choose表示是否至少选了一个；第二步若step==n，若choose==true则更新答案；第三步两个分支：不选（直接递归）和选（sour*=a[step]，bitter+=b[step]，choose=true）。核心思想 ：每个物品只有两种状态，形成二叉搜索树。 错因回溯 1.忘记记录是否选择了至少一个食材，导致空集合参与计算；2.错误剪枝：if(abs(sour-bitter)>ans) return;因为后面加入食材可能降低差值；3.酸度初始值设为0，但酸度是乘积，应设为1。 边界和易错点 1.酸度初始值为1（乘积的单位元）；2.必须记录是否至少选了一个食材；3.不能随意剪枝，因为差值可能先增后减；4.选和不选两个分支都要搜索。 下次看到什么信号，我应该想到这个方法 看到「每个物品选/不选 + 求最优 」，用子集DFS。
AC 完整代码 # include <iostream> # include <cmath> using namespace std; int n; int a[ 15 ] , b[ 15 ] ; int ans= 1e9 ; void dfs ( int step, int sour, int bitter, bool choose) { if ( step== n) { if ( choose) { ans= min ( ans, abs ( sour- bitter) ) ; } return ; } // 分支1：不选 dfs ( step+ 1 , sour, bitter, choose) ; // 分支2：选 dfs ( step+ 1 , sour* a[ step] , bitter+ b[ step] , true ) ; } int main ( ) { cin>> n; for ( int i= 0 ; i< n; i++ ) { cin>> a[ i] >> b[ i] ; } dfs ( 0 , 1 , 0 , false ) ; cout<< ans<< endl; return 0 ; } 三题对比总结 对比维度 P2089 烤鸡 P1036 选数 Perket 枚举类型 排列型 组合型 子集型 状态参数 (step, sum)(step, start, sum)(step, sour, bitter, choose)下一层起点 固定范围 1~3 i+1无（只有选/不选） 是否需要 visited ❌ ❌ ❌ 核心判断 sum == nisPrime(sum)min(abs(sour-bitter))典型信号 每个位置固定选择 n选k，顺序无关 每个物品选/不选
第四部分：填涂颜色（Flood Fill） 基本信息 项目 内容 题目编号、来源 填涂颜色 训练层级 B 图搜索基础 知识版块 DFS、连通块、Flood Fill
解题前・关键信号识别 维度 分析 目标、约束、底层结构 目标 ：将被其他区域包围的0区域染色；约束 ：棋盘大小有限；底层结构 ：棋盘上的连通区域问题。数据规模 n≤30，DFS完全可行。 候选算法和依据 Flood Fill（洪水填充）；依据 ：能够连接到边界的0一定不是被包围的，从边界开始标记所有外部0，剩下的0就是内部区域。 复杂度预判 时间复杂度O(n²)，空间复杂度O(n²)。
解题后・外化复盘 维度 内容 实现结构 / 核心思路 第一步从所有边界上的0开始DFS（或BFS），标记所有外部0为已访问；第二步遍历整个棋盘，所有未被标记的0即为被包围的内部区域，将其改为颜色2；第三步输出修改后的棋盘。核心思想 ：正难则反——不直接找内部0，而是标记外部0，剩下的就是内部0。 错因回溯 1.直接寻找内部0导致判断复杂；2.忘记标记访问导致重复搜索；3.从非边界位置开始搜索，漏掉边界可达的外部0。 边界和易错点 1.必须从边界上的0开始DFS；2.访问过的位置需要标记；3.边界上的0永远属于外部；4.DFS结束后恢复/修改状态。 下次看到什么信号，我应该想到这个方法 看到「棋盘 + 区域 + 内外判断 + 连通 」，用Flood Fill。
AC 完整代码 # include <iostream> # include <vector> # include <set> # include <cmath> # include <algorithm> using namespace std; int n; int v[ 35 ] [ 35 ] ; bool vis[ 35 ] [ 35 ] ; int dx[ ] = { - 1 , 0 , 1 , 0 } ; int dy[ ] = { 0 , 1 , 0 , - 1 } ; void dfs ( int x, int y) { if ( x>= n|| x< 0 || y>= n|| y< 0 ) { return ; } if ( vis[ x] [ y] ) return ; if ( v[ x] [ y] != 0 ) return ; vis[ x] [ y] = true ; for ( int i= 0 ; i< 4 ; i++ ) { int nx= x+ dx[ i] ; int ny= y+ dy[ i] ; dfs ( nx, ny) ; } } int main ( ) { cin>> n; for ( int i= 0 ; i< n; i++ ) { for ( int j= 0 ; j< n; j++ ) { cin>> v[ i] [ j] ; } } for ( int i= 0 ; i< n; i++ ) { dfs ( i, 0 ) ; dfs ( i, n- 1 ) ; } for ( int j= 0 ; j< n; j++ ) { dfs ( 0 , j) ; dfs ( n- 1 , j) ; } for ( int i= 0 ; i< n; i++ ) { for ( int j= 0 ; j< n; j++ ) { if ( v[ i] [ j] == 0 && ! vis[ i] [ j] ) { cout<< 2 << " " ; } else { cout<< v[ i] [ j] << " " ; } } cout<< endl; } return 0 ; 第五部分：迷宫问题（BFS预处理） 基本信息 项目 内容 题目编号、来源 迷宫问题 训练层级 B BFS优化 知识版块 BFS、连通块、预处理
解题前・关键信号识别 维度 分析 目标、约束、底层结构 目标 ：多次询问某个位置所在连通区域大小；约束 ：查询次数可能非常大；底层结构 ：连通区域的大小是固定的，只需预处理一次。数据规模 n≤1000，询问次数可能达1e5。 候选算法和依据 BFS/DFS预处理 + 编号统计；依据 ：一次搜索处理所有连通区域，后续查询O(1)。 复杂度预判 预处理O(n²)，每次查询O(1)。
解题后・外化复盘 维度 内容 实现结构 / 核心思路 第一步遍历所有格子，若当前格子未编号且为可走格子，进行BFS/DFS搜索；第二步搜索过程中为所有可走格子分配相同编号；第三步记录该编号对应的连通块大小；第四步每次查询直接输出cnt[id[x][y]]。核心思想 ：一次预处理所有连通区域，避免每次查询重新搜索。 错因回溯 1.每次查询重新DFS，时间复杂度太高`；2.BFS入队时忘记立即标记访问，导致重复入队。 边界和易错点 1.x表示行，y表示列；2.BFS队列操作正确；3.新加入节点必须立即标记访问，否则可能重复入队；4.数组大小要足够。 下次看到什么信号，我应该想到这个方法 看到「大量询问 + 连通区域 」，用搜索预处理 + 编号统计。
AC 完整代码 # include <iostream> # include <vector> # include <queue> # include <cmath> # include <algorithm> using namespace std; int n, m; string v[ 1005 ] ; int id[ 1005 ] [ 1005 ] ; int cnt[ 1000005 ] ; int dx[ ] = { - 1 , 0 , 1 , 0 } ; int dy[ ] = { 0 , 1 , 0 , - 1 } ; void bfs ( int sx, int sy, int num) { queue< pair< int , int >> q; q. push ( { sx, sy} ) ; id[ sx] [ sy] = num; int size= 0 ; while ( ! q. empty ( ) ) { auto [ x, y] = q. front ( ) ; q. pop ( ) ; size++ ; for ( int i= 0 ; i< 4 ; i++ ) { int nx= x+ dx[ i] ; int ny= y+ dy[ i] ; if ( nx< 0 || nx>= n|| ny< 0 || ny>= n) continue ; if ( id[ nx] [ ny] ) continue ; if ( v[ x] [ y] == v[ nx] [ ny] ) continue ; id[ nx] [ ny] = num; q. push ( { nx, ny} ) ; } } cnt[ num] = size; } int main ( ) { cin>> n>> m; for ( int i= 0 ; i< n; i++ ) { cin>> v[ i] ; } int num= 0 ; for ( int i= 0 ; i< n; i++ ) { for ( int j= 0 ; j< n; j++ ) { if ( id[ i] [ j] == 0 ) { num++ ; bfs ( i, j, num) ; } } } while ( m-- ) { int x, y; cin>> x>> y; x-- ; y-- ; cout<< cnt[ id[ x] [ y] ] << endl; } return 0 ; } 
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
