> 文档中心 > 【备战蓝桥,冲击省一】深度优先搜索(DFS)看完你还能不会?

【备战蓝桥,冲击省一】深度优先搜索(DFS)看完你还能不会?


💟作者简介:大家好,我是Ceylan_,可以叫我CC ❣️    
📝个人主页:Ceylan_的博客
🏆博主信息:平凡的大一学生,有着不平凡的梦

         专栏

  • 【备战蓝桥,冲击省一】

⚡希望大家多多支持😘一起进步~❤️
🌈若有帮助,还请关注➕点赞➕收藏,不行的话我再努努力💪💪💪

🌺深度优先搜索

深度优先搜索就像其名一样,在图中一直深入,深度优先搜索从最近的结点出发进行探索,直到该结点的所有出发结点都被发现为止。一但结点的所有出发边都被发现,则回溯到此结点的前驱结点,搜索前驱结点的未发现出发边。

通俗来讲, 深度优先搜索就是选择一条路一直走到尽头,走到尽头之后后退一步,换一条没走过的路继续走到尽头。

DFS问题一般都可以抽象成为一颗递归树,当遇到DFS问题时不妨画画图试一试。

 我们来看看这颗递归树,从头结点A出发,第一步向左走,到达结点B。第二步从结点B出发,继续向左移动,到达结点C。由于结点C已经走到尽头了,第三步将结点位置回到前驱结点B,第四步B向未走过的路线右边移动,来到结点D。同理,可以依次遍历到全部的可能。

🌺基本模板

 一定要熟悉模板的步骤!!!

int check(参数){if(满足条件)return 1;return 0; }void dfs(int step){if(满足边界条件){进行操作 return; } for(int i=0;i<可操作长度;i++){if(check())满足条件 {修改现场 dfs(下一情况) ;还原现场 }}} 

模板不是一成不变的,要根据题目情况不断变化

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

把 1∼n 这 n个整数排成一行后随机打乱顺序,输出所有可能的次序。

输入格式

一个整数 n。

输出格式

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

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

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

数据范围

1≤n≤9

输入样例:

3

输出样例:

1 2 31 3 22 1 32 3 13 1 23 2 1

思路

 我们来看3这一情况。首先有三个空,从前往后填数字,每次填一个位置,填的数字不能和前面一样。

一开始为【  _ _ _ 】,我们先填入1,变成【  1 _ _ 】

我们填好了第一空位,接下来填第二空位,可以填入2,变成【  1 2 _ 】

我们填好了第二空位,接下来填第三空位,可以填入3,变成【  1 2 3 】

此时没有空位了,符合条件,进行输出。

然后后退一步,变成【  1 2 _ 】,剩下一位没有可以填的数,继续后退,变成【  1 _ _ 】

我们填好了第一空位,接下来填第二空位,由于2出现过一次,这里只能填入3,变成【  1 3 _ 】

我们填好了第二空位,接下来填第三空位,可以填入2,变成【  1 3 2 】

此时没有空位了,符合条件,进行输出。

然后后退一步,变成【  1 3 _ 】,剩下一位没有可以填的数,继续后退,变成【  1 _ _ 】

我们填好了第一空位,接下来填第二空位,由于2,3都出现过,继续后退,变成【  _ _ _ 】

由于第一空位填入过1,现在可以填入2,变成【  2 _ _ 】

我们填好了第一空位,接下来填第二空位,可以填入1,变成【  2 1 _ 】

我们填好了第二空位,接下来填第三空位,可以填入3,变成【  2 1 3 】

此时没有空位了,符合条件,进行输出。

然后后退一步,变成【  2 1 _ 】,剩下一位没有可以填的数,继续后退,变成【  2 _ _ 】

我们填好了第一空位,接下来填第二空位,由于1出现过一次,这里只能填入3,变成【  2 3 _ 】

我们填好了第二空位,接下来填第三空位,可以填入1,变成【  2 3 1 】

此时没有空位了,符合条件,进行输出。

然后后退一步,变成【  2 3 _ 】,剩下一位没有可以填的数,继续后退,变成【  2 _ _ 】

我们填好了第一空位,接下来填第二空位,由于2,3都出现过,继续后退,变成【  _ _ _ 】

由于第一空位填入过1,2,现在可以填入3,变成【  3 _ _ 】

我们填好了第一空位,接下来填第二空位,可以填入1,变成【  3 1 _ 】

我们填好了第二空位,接下来填第三空位,可以填入2,变成【  3 1 2 】

此时没有空位了,符合条件,进行输出。

然后后退一步,变成【  3 1 _ 】,剩下一位没有可以填的数,继续后退,变成【  3 _ _ 】

我们填好了第一空位,接下来填第二空位,由于1出现过一次,这里只能填入2,变成【  3 2 _ 】

我们填好了第二空位,接下来填第三空位,可以填入1,变成【  3 2 1 】

此时没有空位了,符合条件,进行输出。

🔺算法分析:

1️⃣用数组a保存序列

2️⃣用数组used查看数组是否出现

3️⃣如果没有空位,输出序列并后退一位

4️⃣修改使用状态

💬 代码演示:

#includeusing namespace std;int a[10];//保存序列 int used[10];//查看数字是否出现 int n;void dfs(int step){if(step>n){ for(int i = 1; i <= n; i++)//输出方案     cout << a[i] << " "; cout << endl; return;} for(int i=1;i>n;dfs(1);return 0;}

🌺

题目描述

一个如下的 6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列 2 4 6 1 3 5 来描述,第 i 个数字表示在第 i 行的相应位置有一个棋子

如下:

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。

输入格式

一行一个正整数 nnn,表示棋盘是 n×n 大小的。

输出格式

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

输入输出样例

输入

6

输出

2 4 6 1 3 53 6 2 5 1 44 1 5 2 6 34

说明提示

【数据范围】
对于 100% 的数据,6≤n≤13

💬 代码演示:

#includeusing namespace std;int ans[14],used[3][28]={0},sum=0,n;int check(int i,int line){    if((!used[0][i])&&(!used[1][line+i])&&(!used[2][line-i+n])) return 1;    return 0;}void dfs(int line){    if(line>n)    { sum++; if(sum>3) return; else {     for(int i=1;i<=n;i++) printf("%d ",ans[i]);     printf("\n");     return; }    }    for(int i=1;i<=n;i++)    { if(check(i,line)) {     ans[line]=i;     used[0][i]=1; used[1][line+i]=1; used[2][line-i+n]=1;     dfs(line+1);     used[0][i]=0; used[1][line+i]=0; used[2][line-i+n]=0; }    }}int main(){    scanf("%d",&n);    dfs(1);    printf("%d",sum);    return 0;}

🌺每日金句

    学习永远不晚                ——高尔基

     本人不才,如有错误,欢迎各位大佬在评论区指正。有帮助的话还请【关注点赞收藏】,不行的话我再努努力💪💪💪