DFS周测三题题解复盘前言本次周测覆盖了 DFS/BFS 的五大核心模型题号题目模型核心特征1P2089 烤鸡排列型DFS每个位置有固定选择范围2P1036 选数组合型DFS不考虑顺序用start去重3Perket子集型DFS每个物品选/不选两分支4填涂颜色Flood Fill连通块标记内外判断5迷宫问题BFS预处理连通块编号O(1)查询第一部分P2089 烤鸡基本信息项目内容题目编号、来源P2089 洛谷 / 烤鸡训练层级B DFS基础知识版块DFS、排列枚举、回溯、剪枝解题前・关键信号识别维度分析目标、约束、底层结构目标10种调料每种选1~3克使总重量为 n输出所有方案约束n ≤ 10000底层结构每个位置有3种选择形成多分支搜索树。数据规模3^10 59049DFS枚举完全可行。候选算法和依据DFS 回溯依据每个位置有固定选择范围需要枚举所有方案。复杂度预判时间复杂度 O(3^10)空间复杂度 O(10)。解题后・外化复盘维度内容实现结构 / 核心思路第一步定义dfs(step, sum)step 表示当前处理第几种调料sum 表示当前总重量第二步若step 10检查sum n满足则记录方案第三步枚举 i 从 1 到 3path[step] i递归dfs(step1, sumi)。核心思想每个位置枚举所有可能取值递归填下一个位置。错因回溯1. 出口忘记写return导致继续执行2. 剪枝不足只判断sum n未考虑剩余调料的最小/最大贡献边界和易错点1. 出口必须return2. n 的范围是 [10, 30]超出直接输出 03. 剪枝条件sum (10-step) n和sum (10-step)*3 n4. path 数组保存当前方案递归返回后自动覆盖无需显式回溯。下次看到什么信号我应该想到这个方法看到「每个位置有多个固定选择 枚举所有方案」用排列型DFS。AC 完整代码#includeiostream#includevector#includestring#includealgorithmusingnamespacestd;intn;intpath[10];vectorvectorintplans;voiddfs(intstep,intsum){if(sumn)return;if(sum(10-step)n)return;if(sum(10-step)*3n)return;if(step10){if(sumn){plans.push_back(vectorint(path,path10));return;}}for(inti1;i3;i){path[step]i;dfs(step1,sumi);}}intmain(){cinn;if(n10||n30){cout0endl;return0;}dfs(0,0);coutplans.size()endl;for(autop:plans){for(inti0;i10;i){coutp[i] ;}coutendl;}return0;}第二部分P1036 选数基本信息项目内容题目编号、来源P1036 洛谷 / NOIP2002 普及组训练层级A DFS知识版块DFS、组合枚举、素数判断解题前・关键信号识别维度分析目标、约束、底层结构目标从 n 个数中选 k 个求和为素数的方案数约束n ≤ 20底层结构组合枚举顺序无关用 start 参数控制枚举起点。数据规模n ≤ 20组合数 C(20,10) 184756DFS 完全可行。候选算法和依据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(step1, i1, suma[i])。核心思想组合不计顺序下一层从 i1 开始枚举避免重复。错因回溯1. 递归写成dfs(step1, start1, ...)而不是i12. 出口忘记return边界和易错点1. 组合用 start 参数不需要 visited2. 下一层递归传i1不是start13. 出口必须return。下次看到什么信号我应该想到这个方法看到「从 n 个数中选 k 个 顺序无关 判断条件」用组合DFS。AC 完整代码#includeiostreamusingnamespacestd;intn,k,ans;inta[25];boolisPrime(intx){if(x2)returnfalse;if(x2)returntrue;if(x%20)returnfalse;for(inti3;i*ix;i2){if(x%i0)returnfalse;}returntrue;}voiddfs(intstep,intstart,intsum){if(stepk){if(isPrime(sum))ans;return;}for(intistart;in;i){dfs(step1,i1,suma[i]);}}intmain(){cinnk;for(inti0;in;i){cina[i];}dfs(0,0,0);coutansendl;return0;}第三部分Perket基本信息项目内容题目编号、来源Perket训练层级B DFS进阶知识版块DFS、子集枚举、选/不选模型解题前・关键信号识别维度分析目标、约束、底层结构目标选择若干种食材使酸度乘积和苦度和的差的绝对值最小约束每个食材只有选/不选两种状态底层结构子集枚举每个物品两个分支。数据规模n≤102^n完全可行。候选算法和依据DFS回溯依据每个物品选/不选枚举所有子集。复杂度预判时间复杂度O(2^n)空间复杂度O(n)。解题后・外化复盘维度内容实现结构 / 核心思路第一步定义dfs(step, sour, bitter, choose)step表示当前处理第几个食材sour表示当前酸度乘积bitter表示当前苦度和choose表示是否至少选了一个第二步若stepn若choosetrue则更新答案第三步两个分支不选直接递归和选sour*a[step]bitterb[step]choosetrue。核心思想每个物品只有两种状态形成二叉搜索树。错因回溯1.忘记记录是否选择了至少一个食材导致空集合参与计算2.错误剪枝if(abs(sour-bitter)ans) return;因为后面加入食材可能降低差值3.酸度初始值设为0但酸度是乘积应设为1。边界和易错点1.酸度初始值为1乘积的单位元2.必须记录是否至少选了一个食材3.不能随意剪枝因为差值可能先增后减4.选和不选两个分支都要搜索。下次看到什么信号我应该想到这个方法看到「每个物品选/不选 求最优」用子集DFS。AC 完整代码#includeiostream#includecmathusingnamespacestd;intn;inta[15],b[15];intans1e9;voiddfs(intstep,intsour,intbitter,boolchoose){if(stepn){if(choose){ansmin(ans,abs(sour-bitter));}return;}// 分支1不选dfs(step1,sour,bitter,choose);// 分支2选dfs(step1,sour*a[step],bitterb[step],true);}intmain(){cinn;for(inti0;in;i){cina[i]b[i];}dfs(0,1,0,false);coutansendl;return0;}三题对比总结对比维度P2089 烤鸡P1036 选数Perket枚举类型排列型组合型子集型状态参数(step, sum)(step, start, sum)(step, sour, bitter, choose)下一层起点固定范围 1~3i1无只有选/不选是否需要 visited❌❌❌核心判断sum nisPrime(sum)min(abs(sour-bitter))典型信号每个位置固定选择n选k顺序无关每个物品选/不选第四部分填涂颜色Flood Fill基本信息项目内容题目编号、来源填涂颜色训练层级B 图搜索基础知识版块DFS、连通块、Flood Fill解题前・关键信号识别维度分析目标、约束、底层结构目标将被其他区域包围的0区域染色约束棋盘大小有限底层结构棋盘上的连通区域问题。数据规模n≤30DFS完全可行。候选算法和依据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开始DFS2.访问过的位置需要标记3.边界上的0永远属于外部4.DFS结束后恢复/修改状态。下次看到什么信号我应该想到这个方法看到「棋盘 区域 内外判断 连通」用Flood Fill。AC 完整代码#includeiostream#includevector#includeset#includecmath#includealgorithmusingnamespacestd;intn;intv[35][35];boolvis[35][35];intdx[]{-1,0,1,0};intdy[]{0,1,0,-1};voiddfs(intx,inty){if(xn||x0||yn||y0){return;}if(vis[x][y])return;if(v[x][y]!0)return;vis[x][y]true;for(inti0;i4;i){intnxxdx[i];intnyydy[i];dfs(nx,ny);}}intmain(){cinn;for(inti0;in;i){for(intj0;jn;j){cinv[i][j];}}for(inti0;in;i){dfs(i,0);dfs(i,n-1);}for(intj0;jn;j){dfs(0,j);dfs(n-1,j);}for(inti0;in;i){for(intj0;jn;j){if(v[i][j]0!vis[i][j]){cout2 ;}else{coutv[i][j] ;}}coutendl;}return0;第五部分迷宫问题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 完整代码#includeiostream#includevector#includequeue#includecmath#includealgorithmusingnamespacestd;intn,m;string v[1005];intid[1005][1005];intcnt[1000005];intdx[]{-1,0,1,0};intdy[]{0,1,0,-1};voidbfs(intsx,intsy,intnum){queuepairint,intq;q.push({sx,sy});id[sx][sy]num;intsize0;while(!q.empty()){auto[x,y]q.front();q.pop();size;for(inti0;i4;i){intnxxdx[i];intnyydy[i];if(nx0||nxn||ny0||nyn)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;}intmain(){cinnm;for(inti0;in;i){cinv[i];}intnum0;for(inti0;in;i){for(intj0;jn;j){if(id[i][j]0){num;bfs(i,j,num);}}}while(m--){intx,y;cinxy;x--;y--;coutcnt[id[x][y]]endl;}return0;}