掌握蓝桥杯的搜索算法，看这1篇就够了！

掌握蓝桥杯的搜索算法，看这1篇就够了！

蓝桥杯作为国内最具影响力的编程竞赛之一，其考察的算法知识点一直是广大参赛选手关注的重点。其中，搜索算法作为一类很重要且常见的算法，在蓝桥杯中占据着重要的地位。本文将详细介绍DFS（深度优先搜索）和BFS（广度优先搜索）两种基本的搜索算法，并通过蓝桥杯2023年省赛的一道真题来具体说明如何应用这些算法解题。

今天，我们来看蓝桥杯C/C++ B组冠军学长 肖志林 给我们分享——《临考突击蓝桥杯高频考点:搜索题型》。
搜索其实就是“高级的”枚举，很多题目其实都可以用搜索来完成。常见的搜索框架算法有：DFS（深度优先搜索）、BFS（广度优先搜索），进阶搜索：搜索剪枝，A*，折半等等。
👉什么是“DFS”？
DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。

所谓深度优先，就是说每次都尝试向更深的节点走。
👉什么是“BFS”？
而BFS全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。
所谓宽度优先，就是每次都尝试访问同一层的节点， 如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的最短合法路径。换言之，这条路径所包含的边数最小。
在BFS结束时，每个节点都是通过从起点到该点的最短路径访问的。算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。
📝搜索算法题型解题技巧
大部分情况下，我们采用DFS或者BFS的框架，去遍历题目的每个状态，以此来获得最优解。一般来讲，会分为以下5步👇：

1. 建立模型，即状态如何表示。
2. 进行递归搜索，遍历每个状态。
3. （可选）剪枝技巧
4. 计算状态的值，更新最优解
5. 继续递归，或者退出
   这里，我们用蓝桥杯的往届真题📑来举例子：
   该道真题来自2023年省赛，标签：枚举、DFS
   这是一道典型的搜索题目，由于数据范围较小，可以采用暴力枚举的方式进行搜索，具体来说，可以采用深度优先搜索(DFS)的方式：
   首先，我们需要明确题目要求✨：
   题目要求将两种糖果分别分给7个小朋友，每个小朋友得到的糖果总数最少为2个最多为5个，问有多少种不同的分法，糖果必须全部完全分完，只要有其中一个小朋友在两种方案中分到的糖果不完全相同，这两种方案就算作不同的方案。
   接下来，我们需要分析约束/限制条件，给出解题步骤👇。
   在搜索的时候，我们需要对每个小朋友分到的糖果数量进行限制，即每个小朋友分到的糖果总数最少为2个，最多为5个。
   在满足这个限制条件下，我们需要对每个小朋友分到的糖果种类进行枚举，由于每个小朋友可以分到两种糖果🍬，所以，对于每个小朋友，我们需要枚举他分到第一种糖果的数量，从而推出他分到第二种糖果的数量。
   不过，在枚举的过程中需要注意一些细节，比如：

• 分到第一种糖果的数量不能超过该种糖果的总数
• 分到第二种糖果的数量不能超过该种糖果的总数
• 每个小朋友分到的两种糖果数量之和不能超过5个
  最后，我们需要给出详细的解题步骤。
  由于这是一道搜索题目，我们可以采用📍深度优先搜索(DFS)的方式进行求解，具体来说：
• 我们可以写一个递归函数dfs(n,m,u)，其中n表示第一种糖果的数量，m 表示第二种糖果的数量，u表示当前正在分配糖果的小朋友的编号。
• 在递归的过程中，我们需要对每个小朋友分到的糖果数量进行限制，这个限制条件可以放在函数的参数中进行传递，也可以放在函数内部进行检查
• 具体来说，每次递归到下一个小朋友时，我们需要枚举他分到第一种糖果的数量，从而推出他分到第二种糖果的数量。
  在枚举的过程中，需要注意一些细节，比如：
• 分到第一种糖果的数量不能超过该种糖果的总数
• 分到第二种糖果的数量不能超过该种糖果的总数
• 每个小朋友分到的两种糖果数量之和不能超过5个。
  递归的出口是：当目前正在分配糖果的小朋友的编号为7时，需要判断第七个小朋友分到的糖果数量是否满足限制条件？如果满足，则累加答案。
  最后，需要注意一些细节问题，比如：
  ✅需要将答案初始化为0
  ✅需要在递归出口处判断第七个小朋友分到的糖果数量是否满足限制条件
  ✅适当把不满足条件的方案进行减枝
  在每一层的搜索中，每个小朋友最多有9种可能的糖果分配情况，而最多只需要枚举5种糖果分配情况，因此，每层最多只需要进行10次搜索。
  由于总共需要进行7层搜索，所以，总的搜索次数不会超过10^7次。
  这也进一步说明了，这道题目的时间复杂度是可以接受的，可以用暴力枚举的方式进行求解。
  ✍解题思路：
  dfs枚举出种植哪些树（暴力枚举）
  🚀优化思路：
  提前算出哪些树不能会相交。
  搜索是一类很重要和常见的算法，掌握好搜索算法，基本能解决大部分毫无头绪的问题。
  但是，搜索算法往往时间或者空间上限制较大，这时候就需要考虑其他算法。不过，从另一方面来说，即使是考察其他算法的题目，搜索算法仍能帮你得到部分分数。对于一部分题目（规律类的数学题），使用搜索也可能帮助你发现一些不易察觉的规律。