【AcWing】蓝桥杯备赛-深度优先搜索-dfs（1）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【AcWing】蓝桥杯备赛-深度优先搜索-dfs（1）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

写在前面：

题目：92. 递归实现指数型枚举 - AcWing题库

读题：

输入格式：

输出格式：

数据范围：

输入样例：

输出样例：

解题思路：

代码：

AC ！！！！！！！！！！

写在最后：

写在前面：

距离蓝桥杯已经不足一个月了，

根据江湖上的传言，

蓝桥杯最喜欢考的是深度优先搜索和动态规划，

所以蓝桥杯也叫暴搜杯、dp杯，

那我备赛当然也就从深度优先搜索，也就是所谓的dfs开始。

题目：92. 递归实现指数型枚举 - AcWing题库

读题：

【AcWing】蓝桥杯备赛-深度优先搜索-dfs（1）,蓝桥杯备赛,算法,dfs,学习,蓝桥杯,深度优先

输入格式：

输入一个整数 n。

输出格式：

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围：

1 ≤ n ≤ 15

输入样例：

输出样例：

解题思路：

这道题是深度优先搜索的经典题目，

我们使用深度优先搜索的时候，

第一个要注意的点是，我们要保证，

我们写出的递归结构能够遍历所有情况，

在我们初学搜索的时候，我们一定要画一个递归搜索树观察，

递归非常抽象，画图能很好的帮助我们解题。（以上递归搜索的基本思路，多熟悉总是好的）

接下来是具体思路：

题目要求我们随机选取输出每种方案，而且要求升序输出。

我们根据要求，画出对应的搜索树：（以n=3为例）

首先是根节点：

【AcWing】蓝桥杯备赛-深度优先搜索-dfs（1）,蓝桥杯备赛,算法,dfs,学习,蓝桥杯,深度优先

递归搜索：

【AcWing】蓝桥杯备赛-深度优先搜索-dfs（1）,蓝桥杯备赛,算法,dfs,学习,蓝桥杯,深度优先

因为题目要求是升序数组，所以从第二个位置开始，

就只能填2，再下一个就得填3，以满足题目要求：

继续搜索：

【AcWing】蓝桥杯备赛-深度优先搜索-dfs（1）,蓝桥杯备赛,算法,dfs,学习,蓝桥杯,深度优先

如果位置已经使用过了，就搜索下一个位置，

没有位置就停下。

最后：

【AcWing】蓝桥杯备赛-深度优先搜索-dfs（1）,蓝桥杯备赛,算法,dfs,学习,蓝桥杯,深度优先

我们根据画出来的搜索树写代码：

代码：

//养成好习惯，先把常用头文件包了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

//数组的大小，比题目要求大即可（题目要求n是小于等于15的）
const int N = 20;

//全局变量的数组会把数组元素初始化成0
int st[N];

//这个是需要输入的变量
int n;

void dfs(int u)
{
    //数组已经存了n个数，达成条件就可以打印了
    if(u == n)
    {
        for(int i = 0; i < n; i++)
        {
            //st数组元素 == 1 表示这个位置需要输出
            if(st[i] == 1)
            {
                printf("%d ", i + 1);
            }
        }
        puts("");
        return;
    }
    else
    {
        //把数组设为1表示该位置写入了数据
        st[u] = 1;
        dfs(u + 1);
        st[u] = 0;
        
        //把数组设为2表示该位置为空
        st[u] = 2;
        dfs(u + 1);
        st[u] = 0;
    }
}

int main()
{
    scanf("%d", &n);
    dfs(0);
    return 0;
}