CSP-J备考冲刺：深度优先搜索(DFS)在近年T3真题中的妙用
CSP-J备考冲刺：深度优先搜索(DFS)在近年T3真题中的妙用
“
高效掌握DFS，助力信息学竞赛
各位备战CSP-J的同学们，11月份的竞赛即将到来，相信大家都在紧张备考中。今天老马将带大家深度剖析深度优先搜索（DFS）这一重要算法在CSP-J近年T3题目中的应用。
为什么DFS如此重要？
深度优先搜索是信息学竞赛中最基础也是最重要的算法之一，几乎每年都会在CSP-J的T3或T4题目中出现。
掌握DFS不仅能够解决搜索类问题，还能为学习更高级的回溯、剪枝算法打下坚实基础。
真题解析1：CSP-J 2024 小木棍
【提交】
https://www.luogu.com.cn/problem/P11229
【问题描述】
小 S 喜欢收集小木棍。在收集了 根长度相等的小木棍之后，他闲来无事，便用它们拼起了数字。用小木棍拼每种数字的方法如下图所示。
现在小 S 希望拼出一个正整数，满足如下条件：
拼出这个数恰好使用 根小木棍；
拼出的数没有前导 ；
在满足以上两个条件的前提下，这个数尽可能小。
小 S 想知道这个数是多少，可 很大，把木棍整理清楚就把小 S 折腾坏了，所以你需要帮他解决这个问题。如果不存在正整数满足以上条件，你需要输出 进行报告。
【输入描述】
本题有多组测试数据。
输入的第一行包含一个正整数 ，表示数据组数。
接下来包含 组数据，每组数据的格式如下：
一行包含一个整数 ，表示木棍数。
【输出描述】
对于每组数据：输出一行，如果存在满足题意的正整数，输出这个数；否则输出 。
【样例输入1】
5
1
2
3
6
18
【样例输出1】
-1
1
7
6
208
【样例解释1】
对于第一组测试数据，不存在任何一个正整数可以使用恰好一根小木棍摆出，故输出 。
对于第四组测试数据，注意 并不是一个满足要求的方案。摆出 、以及 都恰好需要 根小木棍，但它们不是摆出的数最小的方案。
对于第五组测试数据，摆出 需要 根小木棍。可以证明摆出任何一个小于 的正整数需要的小木棍数都不是 。注意尽管拼出 也需要 根小木棍，但因为这个数有前导零，因此并不是一个满足要求的方案。
【数据范围】
对于所有测试数据，保证：，。
特殊性质 A：保证 是 的倍数且 。
特殊性质 B：保证存在整数 使得 ，且 。
参考答案：
这是一个典型的DFS+剪枝+贪心问题。我们需要在满足条件的解空间中，找到最小的正整数。
/*
* [CSP-J 2024] 小木棍
* https://www.luogu.com.cn/problem/P11229
*/
# include
# include
using namespace std;
intarr[10] = { 6,2,5,5,4,5,6,3,7,6};
intidx;//位数
voiddfs(intx, intrest)
{
// x表示第x位
// rest表示剩下rest个小木棍
if(x == idx + 1)
{
for(inti = 1; i <= idx; i++)
{
cout<< res[i];
}
cout<< endl;
return;
}
for(inti = 0; i < 10; i++)
{
if(i == 0&& x == 1)
{
continue;
}
// 只要i满足条件，填到第x位，直接break
if(rest - arr[i] >= 2* (idx - x) && rest - arr[i] <= 7* (idx - x))
{
res[x] = i;
dfs(x + 1, rest - arr[i]);
break;
}
}
}
intmain
{
intt;
cin>> t;
for(inti = 0; i < t; i++)
{
intn;
cin>> n;
// 除了-1之外，任何小木棍数量都可以够成一个数字
if(n == 1)
{
cout<< -1<< endl;
continue;
}
//数字小，位数一定最少，位数最少，再去找小的数字
idx = ceil(n / 7.0);
dfs(1, n);
}
return 0;
}
真题解析2：CSP-J 2017 棋盘
【提交】
https://www.luogu.com.cn/problem/P3956
【问题描述】
有一个 的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 个金币。
另外， 你可以花费 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。
现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？
【输入描述】
第一行包含两个正整数 ，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。
接下来的 行，每行三个正整数 ， 分别表示坐标为 的格子有颜色 。
其中 代表黄色，代表红色。 相邻两个数之间用一个空格隔开。 棋盘左上角的坐标为 ，右下角的坐标为 。
棋盘上其余的格子都是无色。保证棋盘的左上角，也就是 一定是有颜色的。
【输出描述】
一个整数，表示花费的金币的最小值，如果无法到达，输出 -1。
【样例输入1】
5 7
1 1 0
1 2 0
2 2 1
3 3 1
3 4 0
4 4 1
5 5 0
【样例输出1】
8
【样例解释1】
棋盘的颜色如下表格所示，其中空白的部分表示无色。
从 开始，走到 不花费金币。
从 向下走到 花费 枚金币。
从 施展魔法，将 变为黄色，花费 枚金币。
从 走到 不花费金币。
从 走到 不花费金币。
从 走到 花费 枚金币。
从 走到 花费 枚金币。
从 施展魔法，将 变为黄色，花费 枚金币。
从 走到 不花费金币。
从 走到 花费 枚金币。
共花费 枚金币。
【样例输入2】
5 5
1 1 0
1 2 0
2 2 1
3 3 1
5 5 0
【样例输出2】
-1
【样例解释2】
棋盘的颜色如下表格所示，其中空白的部分表示无色。
从 走到 ，不花费金币。
从 走到 ，花费 金币。
施展魔法将 变为黄色，并从 走到 花费 金币。
从 走到 不花费金币。
从 只能施展魔法到达 。
而从以上四点均无法到达 ，故无法到达终点，输出。
【数据范围】
对于 的数据，。
对于 的数据，。
对于 的数据，。
参考答案：
需要在彩色棋盘上找到从左上角到右下角的最小花费路径，涉及颜色变化和魔法使用，这是一个典型的DFS+记忆化应用。
#include
#include
#include
#include
using namespace std;
intdx[4] = { 1, -1, 0, 0};
intdy[4] = { 0, 0, 1, -1};
intm, n;
vector<vector<int>> color; // 存储颜色：-1无色，0红色，1黄色
vector<vector<int>> minCost; // 到达每个格子的最小花费
voiddfs(intx, inty, intcost, boolusedMagic)
{
// 剪枝：如果当前花费已经大于已知最小花费，直接返回
if(cost >= minCost[x][y])
{
return;
}
minCost[x][y] = cost;
// 到达终点
if(x == m && y == m)
{
return;
}
for(inti = 0; i < 4; i++)
{
intnx = x + dx[i];
intny = y + dy[i];
// 越界检查
if(nx < 1|| nx > m || ny < 1|| ny > m)
{
continue;
}
// 情况1：目标格子有颜色
if(color[nx][ny] != -1) {
if(color[nx][ny] == color[x][y])
{
// 颜色相同，不花费金币
dfs(nx, ny, cost, false);
}
else
{
// 颜色不同，花费1金币
dfs(nx, ny, cost + 1, false);
}
}
// 情况2：目标格子无色，且当前未处于魔法产生的格子
elseif(usedMagic == false)
{
// 施展魔法，花费2金币，将无色格子变为当前格子的颜色
color[nx][ny] = color[x][y]; // 暂时改变颜色
dfs(nx, ny, cost + 2, true); // 标记为使用过魔法
color[nx][ny] = -1; // 回溯，恢复无色
}
}
}
intmain
{
cin>> m >> n;
// 初始化vector二维数组，大小为(m+1)×(m+1)，初始值为-1
color.resize(m + 1, vector<int>(m + 1, -1));
// 初始化minCost为(m+1)×(m+1)，初始值为INF
minCost.resize(m + 1, vector<int>(m + 1, INT_MAX));
// 读入有颜色的格子
for(inti = 0; i < n; i++)
{
intx, y, c;
cin>> x >> y >> c;
color[x][y] = c;
}
// 从起点开始DFS
dfs(1, 1, 0, false);
// 输出结果
if(minCost[m][m] == INT_MAX)
{
cout<< -1<< endl;
}
else
{
cout<< minCost[m][m] << endl;
}
return 0;
}
DFS备考技巧
状态设计是关键：合理定义DFS状态参数，包含问题的所有维度
剪枝是效率保障：及时剪去不可能产生最优解的分支
记忆化避免重复：对已计算的状态进行记录，提高效率
注意边界条件：递归终止条件要考虑全面
重新实现上述两道真题，确保完全理解
尝试使用DFS解决迷宫问题、八皇后问题等经典题目
练习剪枝技巧，思考如何优化搜索效率
离比赛还有一段时间，只要大家坚持练习，掌握DFS的核心思想，一定能在CSP-J中取得好成绩！
老马温馨提示：DFS虽好，但也要注意避免栈溢出问题。在问题规模较大时，考虑使用迭代加深或BFS等替代方案。
祝各位考生备考顺利，赛场得意！
青少年编程竞赛交流