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>usingnamespacestd;intn;intpath[10];vector<vector<int>>plans;voiddfs(intstep,intsum){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(inti=1;i<=3;i++){path[step]=i;dfs(step+1,sum+i);}}intmain(){cin>>n;if(n<10||n>30){cout<<0<<endl;return0;}dfs(0,0);cout<<plans.size()<<endl;for(auto&p:plans){for(inti=0;i<10;i++){cout<<p[i]<<" ";}cout<<endl;}return0;}第二部分：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>usingnamespacestd;intn,k,ans;inta[25];boolisPrime(intx){if(x<2)returnfalse;if(x==2)returntrue;if(x%2==0)returnfalse;for(inti=3;i*i<=x;i+=2){if(x%i==0)returnfalse;}returntrue;}voiddfs(intstep,intstart,intsum){if(step==k){if(isPrime(sum))ans++;return;}for(inti=start;i<n;i++){dfs(step+1,i+1,sum+a[i]);}}intmain(){cin>>n>>k;for(inti=0;i<n;i++){cin>>a[i];}dfs(0,0,0);cout<<ans<<endl;return0;}第三部分：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>usingnamespacestd;intn;inta[15],b[15];intans=1e9;voiddfs(intstep,intsour,intbitter,boolchoose){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);}intmain(){cin>>n;for(inti=0;i<n;i++){cin>>a[i]>>b[i];}dfs(0,1,0,false);cout<<ans<<endl;return0;}三题对比总结
| 对比维度 | P2089 烤鸡 | P1036 选数 | Perket |
|---|---|---|---|
| 枚举类型 | 排列型 | 组合型 | 子集型 |
| 状态参数 | (step, sum) | (step, start, sum) | (step, sour, bitter, choose) |
| 下一层起点 | 固定范围 1~3 | i+1 | 无（只有选/不选） |
| 是否需要 visited | ❌ | ❌ | ❌ |
| 核心判断 | sum == n | isPrime(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>usingnamespacestd;intn;intv[35][35];boolvis[35][35];intdx[]={-1,0,1,0};intdy[]={0,1,0,-1};voiddfs(intx,inty){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(inti=0;i<4;i++){intnx=x+dx[i];intny=y+dy[i];dfs(nx,ny);}}intmain(){cin>>n;for(inti=0;i<n;i++){for(intj=0;j<n;j++){cin>>v[i][j];}}for(inti=0;i<n;i++){dfs(i,0);dfs(i,n-1);}for(intj=0;j<n;j++){dfs(0,j);dfs(n-1,j);}for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(v[i][j]==0&&!vis[i][j]){cout<<2<<" ";}else{cout<<v[i][j]<<" ";}}cout<<endl;}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 完整代码
#include<iostream>#include<vector>#include<queue>#include<cmath>#include<algorithm>usingnamespacestd;intn,m;string v[1005];intid[1005][1005];intcnt[1000005];intdx[]={-1,0,1,0};intdy[]={0,1,0,-1};voidbfs(intsx,intsy,intnum){queue<pair<int,int>>q;q.push({sx,sy});id[sx][sy]=num;intsize=0;while(!q.empty()){auto[x,y]=q.front();q.pop();size++;for(inti=0;i<4;i++){intnx=x+dx[i];intny=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;}intmain(){cin>>n>>m;for(inti=0;i<n;i++){cin>>v[i];}intnum=0;for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(id[i][j]==0){num++;bfs(i,j,num);}}}while(m--){intx,y;cin>>x>>y;x--;y--;cout<<cnt[id[x][y]]<<endl;}return0;}
 agent和组件)