【AcWing】蓝桥杯备赛-深度优先搜索-dfs(2)

简介: 【AcWing】蓝桥杯备赛-深度优先搜索-dfs(2)

写在前面:

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


根据江湖上的传言,


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


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


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


题目:94. 递归实现排列型枚举 - AcWing题库

读题:


输入格式:

一个整数 n。


输出格式:

按照从小到大的顺序输出所有方案,每行 1 个。


首先,同一行相邻两个数用一个空格隔开。


其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。


数据范围:

1 ≤ n ≤ 9


输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

解题思路:

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


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


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


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


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


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


接下来是具体思路:


根据题目说的从小到大输出每个方案,


字典序小的数放在前面,


我们画一个递归搜索树观察:


根节点:(以n=3为例)



向下搜索:


从小到大:



继续搜索,


使用过得数不再使用:



继续搜索:

我们需要输出的就是最下面这一排。


下面是代码实现:


代码:

//养成好习惯,把常用头文件包了
#include 
#include 
#include 
#include 
using namespace std;
//数组大小比题目要求大就行,这题n <= 9
const int N = 10;
int n;
int st[N];
//创建一个数组用来判断位置是否已经有数据了
bool used[N];
void dfs(int u)
{
    //已经递归搜索到底了
    if(u == n)
    {
        //打印数组中存放的值
        for(int i = 0; i < n; i++)
        {
            printf("%d ", st[i]);
        }
        puts("");
        return;
    }
    else
    {
        for(int i = 0; i < n; i++)
        {
            //如果used[i]等于true,证明该位置已经被占用,直接让i++继续循环
            if(!used[i])
            {
                //表示该位置已经占用
                used[i] = true;
                //将要打印的值存进数组
                st[u] = i + 1;
                //递归往下搜索
                dfs(u + 1);
                //位置恢复原样(没有被占用了)
                used[i] = false;
            }
        }
    }
}
int main()
{
    scanf("%d", &n);
    dfs(0);
    return 0;
}

AC !!!!!!!!!!


写在最后:

以上就是本篇文章的内容了,感谢你的阅读。


如果喜欢本文的话,欢迎点赞和评论,写下你的见解。


如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。


之后我还会输出更多高质量内容,欢迎收看。


相关文章
|
算法
【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(3)
【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(3)
113 0
|
算法 定位技术
【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(7)
【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(7)
108 0
|
算法
【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(2)
【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(2)
116 0
|
存储 算法
【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs(14)
【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs(14)
112 0
|
安全 算法
【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs(16)
【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs(16)
120 0
|
机器学习/深度学习 算法 定位技术
【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs(15)
【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs(15)
113 0
|
程序员 定位技术 C++
[蓝桥杯] 双指针、BFS和DFS与图论问题
本篇文章针对蓝桥杯比赛的考点,列出双指针、BFS和DFS与图论的相关习题以及知识点的解释。希望本篇文章会对你有所帮助。
92 0
|
机器学习/深度学习
【AcWing】蓝桥杯备赛-深度优先搜索-dfs(3)
【AcWing】蓝桥杯备赛-深度优先搜索-dfs(3)
101 0
【AcWing】蓝桥杯备赛-深度优先搜索-dfs(1)
【AcWing】蓝桥杯备赛-深度优先搜索-dfs(1)
73 0
|
机器学习/深度学习 算法
【AcWing刷题】蓝桥杯专题突破-深度优先搜索-dfs(8)
【AcWing刷题】蓝桥杯专题突破-深度优先搜索-dfs(8)
104 0