【刷题】备战蓝桥杯 — dfs 算法

送给大家一句话：

风度真美！
即使流泪，也要鼓掌，
即使失望，也要满怀希望。
——刘宝增

dfs 算法

• 1 前言
• 2 洛谷 P1030 [NOIP2001 普及组] 求先序排列
• • 题目描述
  • 算法思路
• 3 洛谷 P1294 高手去散步
• • 题目描述
  • 算法思路
• 4 蓝桥真题 十三届省赛 飞机降落
• • 题目描述
  • 算法思路
• 5 总结
• Thanks♪(･ω･)ﾉ谢谢阅读！！！
• 下一篇文章见！！！

1 前言

在蓝桥杯的比赛中，深度优先搜索（DFS，Depth-First Search）算法是一种常用的搜索算法，它通过尽可能深地搜索树的分支，来寻找解决方案。由于其简单和易于实现的特性，DFS成为解决问题的强大工具，尤其是在数据规模较小的情况下。数据在100以内一般使用dfs

运行原理： DFS算法的核心思想是从一个起点开始，沿着树的边走到尽可能深的分支上，然后回溯到之前的分叉点，寻找未探索的分支。这个过程重复进行，直到找到解决方案或探索完所有可能的路径。DFS通常使用递归实现，这使得代码简洁易读。它利用栈（递归调用栈）来记录访问路径，从而实现回溯功能。基本蓝桥杯dfs算法题型可以使用以下模版：

#include //视情况而定#define int long long #define endl \'\\n\'#define N 1001using namespace std;//往往需要一个哈希表来辅助判断int vis[N] = { 0};void dfs(){ //退出条件很重要！！！if() return ;for(){ //跟新结果//继续深入dfs();//回溯}}signed main(){ //加快读写速度 也可以直接使用C语言标准输入输出函数ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//多组数据int t = 0; cin >> t;while(t--){ //进行基础读入数据//构建图 ，记录结构体等//解决问题dfs();}return 0；}

常用于以下题型：

1. 路径问题： 寻找从起点到终点的路径，或者求解所有可能的路径。
2. 排列组合问题： 需要枚举出所有可能的情况时，如全排列、组合选择。
3. 连通性问题： 如判断图中两个节点是否连通，或者求解连通分量。
4. 解谜与回溯问题： 如N 皇后问题、迷宫探索、数独解题等。

注意事项：

• 栈溢出问题（一般不用考虑）： 由于DFS使用递归实现，深度过大时可能会导致栈溢出。针对这一点，可以尝试使用迭代深化搜索（IDS）或非递归方式实现DFS。
• 重复状态处理（一定要仔细）： 在搜索过程中可能会遇到重复状态，如果不加以处理，可能会导致算法陷入无限循环。通常使用访问标记（如访问数组）来避免重复访问。
• 选择合适的剪枝策略（尽力而行）： 合理的剪枝可以显著提高DFS的效率。通过预先判断某些路径是否可能达到目标，从而避免无效搜索。

通过以上的解析，我们可以看到DFS不仅在蓝桥杯中，在很多算法竞赛和实际问题解决中都是一个非常实用的工具。它虽然在处理大数据量时可能会遇到性能瓶颈，但在数据量适中、需要深度搜索解决方案的问题上，DFS仍然是一个十分可靠的选择。
下面我们来一起做几道竞赛题目来试试手！

2 洛谷 P1030 [NOIP2001 普及组] 求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ≤8）

输入格式
共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式
共一行一个字符串，表示一棵二叉树的先序。

根据题目，我们需要通过二叉树的中序遍历和后序遍历来写出前序遍历的结果。对于二叉树的确定单凭中序遍历或者后序遍历是不可能的，只有两者结合才能确定一棵完整的二叉树！来看样例：

• 输入
  BADC
  BDCA
• 输出
  ABCD

我们可以画出树的结构：

这样前序遍历的结果就有了

算法思路

这道题涉及了二叉树，那么如果不使用dfs 就会非常复杂捏！所以我们把解题交给dfs,重重递归解决问题：

1. 首先通过后序遍历 ， 我们可以确定根节点 （输出打印）
2. 通过在中序遍历中找到根节点的位置，可以区分左右子树
3. 区分出左右子树后，就可以继续寻找左右子树的根节点 ，重复1 - 2操作即可。

#include#include#define int long