备战蓝桥杯————深度优先搜索(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;}
[USACO1.5]八皇后 Checker Challenge - 洛谷🌺[USACO1.5]八皇后 Checker Challenge - 洛谷
题目描述
一个如下的 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;}
🌺每日金句
学习永远不晚 ——高尔基
本人不才,如有错误,欢迎各位大佬在评论区指正。有帮助的话还请【关注➕点赞➕收藏】,不行的话我再努努力💪💪💪