算法伴学笔记 Day 01 | DFS入门
⭐纵星河万里，亦不及你一垂眸。 –Samsara_soul
🙌题单（List-DFS 01)
由浅入深 循序渐进
📋A 洛谷-P2089 烤鸡
Label 指数型枚举 模板本板 Level 普及-
📋B 洛谷-P1088 [NOIP2004 普及组] 火星人
Label 排列型枚举 可行性剪枝 Level 普及-
📋C 洛谷-P1149 [NOIP2008 提高组] 火柴棒等式
Label 指数型枚举 可行性剪枝 Level 普及-
📋D 洛谷-P1219 [USACO1.5] 八皇后 Checker Challenge
Label 暴力搜索 模板 Level 普及/提高-
题型分类 参考博客 DFS（深度优先搜索）8种题型
剪枝策略 参考博客 深搜的剪枝技巧C++详解
友情链接 哔哩哔哩-DFS正确入门方式 | DFS + 递归与递推习题课(上) | 一节课教你爆搜!
—A 题 详 解—
🟢原题回顾🟢
📋A 洛谷-P2089 烤鸡
Label 指数型枚举 Level 普及-
题目背景
猪猪 Hanke 得到了一只鸡。
题目描述
猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有
10
10
10 种配料（芥末、孜然等），每种配料可以放
1
1
1 到
3
3
3 克，任意烤鸡的美味程度为所有配料质量之和。
加入每种配料质量有三种选择，共加入十种配料，可能方案数
N
=
3
10
=
59049
N=3^{10}=59049
N=310=59049
现在， Hanke 想要知道，如果给你一个美味程度
n
n
n ，请输出这
10
10
10 种配料的所有搭配方案。
输入格式
一个正整数
n
n
n，表示美味程度。
输出格式
第一行，方案总数。
题目要求先输出方案总数res，而方案总数需要在搜索结束时才可得到。因此，需要使用数组mem[][10]存储可行方案
第二行至结束，
10
10
10 个数，表示每种配料所放的质量，按字典序排列。
每种配料方案数为3，故而是指数型枚举
什么是字典序 ⭐参考 百度百科-字典序
如果没有符合要求的方法，就只要在第一行输出一个
0
0
0。
样例 #1
样例输入 #1
11
样例输出 #1
10 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1
提示
对于
100
%
100\%
100% 的数据，
n
≤
5000
n \leq 5000
n≤5000。
原题回顾 END
🟢AC代码及注解🟢
#include
using namespace std;
const int N = 12; //略开大些亦可
int n; // 食材美味度 输入数据
int arr[N]; //存放当前方案
int res; //记录方案数
int mem[10000][N]; // 用于记录答案
void dfs(int x,int sum) //x表示搜索到的层数 sum表示当前食物美味度
{
if(sum > n) return ; //可行性剪枝
if(x>10){ //遍历到第十项
if(sum == n){ //满足要求的解
res++; //计数器++
for(int i=1;i<=10;i++){
mem[res][i]=arr[i]; //存放可行解
}
}
return ; //注意return位置 不在if语句内
}
for(int i=1;i<=3;i++) //遍历过程
{
arr[x] = i; //记录步骤到当前方案
dfs(x+1,sum+i);
arr[x] = 0; //重置步骤
}
}
int main()
{
cin >> n;
dfs(1,0); //从第一项起搜索
//以下为打印答案
cout << res << "\n";
for(int i=1;i<=res;i++)
{
for(int j=1;j<=10;j++)
{
cout << mem[i][j] <<" ";
}
cout << "\n";
}
return 0;
}
🟢洛谷评测🟢
—B 题 详 解—
🟢原题回顾🟢
📋B 洛谷-P1088 [NOIP2004 普及组] 火星人
Label 排列型枚举 可行性剪枝 Level 普及-
题目描述
人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。
步骤 ——1.破解含义 2.加上一个较小数 3.翻译结果
火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为
1
,
2
,
3
,
⋯
1,2,3,\cdots
1,2,3,⋯。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。
一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为
1
,
2
,
3
,
4
1,2,3,4
1,2,3,4 和
5
5
5，当它们按正常顺序排列时，形成了
5
5
5 位数
12345
12345
12345，当你交换无名指和小指的位置时，会形成
5
5
5 位数
12354
12354
12354，当你把五个手指的顺序完全颠倒时，会形成
54321
54321
54321，在所有能够形成的
120
120
120 个
5
5
5 位数中，
12345
12345
12345 最小，它表示
1
1
1；
12354
12354
12354 第二小，它表示
2
2
2；
54321
54321
54321 最大，它表示
120
120
120。下表展示了只有
3
3
3 根手指时能够形成的
6
6
6 个
3
3
3 位数和它们代表的数字：
| 三进制数 | 代表的数字 |
|---|---|
|
123 123 123 | 1 1 1 |
132 132 132 | 2 2 2 |
213 213 213 | 3 3 3 |
231 231 231 | 4 4 4 |
312 312 312 | 5 5 5 |
321 321 321 | 6 6 6 |
显而易见的是 火星人的每根手指都是唯一的，不可能在两个位置同时出现。手指序列即1~n的全排列【排列型枚举】
现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。
输入格式
共三行。
第一行一个正整数
N
N
N，表示火星人手指的数目（
1
≤
N
≤
10000
1 \le N \le 10000
1≤N≤10000）。
第二行是一个正整数
M
M
M，表示要加上去的小整数（
1
≤
M
≤
100
1 \le M \le 100
1≤M≤100）。
下一行是
1
1
1 到
N
N
N 这
N
N
N 个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。
输出格式
N
N
N 个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。
样例 #1
样例输入 #1
5 3 1 2 3 4 5
样例输出 #1
1 2 4 5 3
提示
对于
30
%
30\%
30% 的数据，
N
≤
15
N \le 15
N≤15。
对于
60
%
60\%
60% 的数据，
N
≤
50
N \le 50
N≤50。
对于
100
%
100\%
100% 的数据，
N
≤
10000
N \le 10000
N≤10000。
原题回顾 END
🟢详解🟢
不剪枝代码（WA示例）
#include
using namespace std;
const int N = 10010; //外星人手指数不超过10000
int n; // 外星人手指数 输入数据
int m; // 要加上的小数 输入数据
int mars[N]; // 记录外星人初始排列 输入数据
int arr[N]; // 记录当前外星人手指序
bool st[N]; // 记录是否被选（手指是唯一的 一根手指不能同时出现在两个地方）
int res; //记录递增次数
//bool return0 = false; //停止标志
void dfs(int x)
{
//if (return0)
// return;
if (x > n){ //遍历到尾部
res++;
if (res == m + 1){ //目标答案在此
//return0 = true;
for (int i = 1; i <= n; i++){
cout << arr[i] << " "; //输出答案
}
}
return;
}
for (int i = 1; i <= n; i++){
if (!res){ //最重要的一步 需要基于外星人所给数字开始遍历
i = mars[x];
}
if (!st[i]){
arr[x] = i;
st[i] = true;
dfs(x + 1);
arr[x] = 0;
st[i] = false;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++){
scanf("%d", &mars[i]);
}
dfs(1);
return 0;
}
评测结果
过程分析
此代码运行过程中到达指定解处可以输出正确答案，但是搜索继续向后进行，时间开销过大。
此时不难看出题目中较小数之深意
优化
增加bool return0 = false; //停止标志
dfs函数修改
void dfs(int x)
{
if (return0)
return;
if (x > n){ //遍历到尾部
res++;
if (res == m + 1){ //目标答案在此
return0 = true;
for (int i = 1; i <= n; i++){
cout << arr[i] << " "; //输出答案
}
}
return;
}
for (int i = 1; i <= n; i++){
if (!res){ //最重要的一步 需要基于外星人所给数字开始遍历
i = mars[x];
}
if (!st[i]){
arr[x] = i;
st[i] = true;
dfs(x + 1);
arr[x] = 0;
st[i] = false;
}
}
}
至此 dfs搜到正确答案后即可华丽退出🙌
洛谷评测
—C 题 详 解—
🟢原题回顾🟢
📋C 洛谷-P1149 [NOIP2008 提高组] 火柴棒等式
Label 排列型枚举 可行性剪枝 Level 普及-
题目描述
给你
n
n
n 根火柴棍，你可以拼出多少个形如
A
+
B
=
C
A+B=C
A+B=C 的等式？等式中的
A
A
A、
B
B
B、
C
C
C 是用火柴棍拼出的整数（若该数非零，则最高位不能是
0
0
0）。用火柴棍拼数字
0
∼
9
0\sim9
0∼9 的拼法如图所示：
注意：
- 加号与等号各自需要两根火柴棍；
- 如果
A
≠
B
A\neq B
A=B，则
A
+
B
=
C
A+B=C
A+B=C 与
B
+
A
=
C
B+A=C
B+A=C 视为不同的等式（
A
,
B
,
C
≥
0
A,B,C\geq0
A,B,C≥0）；
n
n
n 根火柴棍必须全部用上。
所有等式都含有+ 与 -其共耗费四根火柴棍，此项火柴开销固定
输入格式
一个整数
n
(
1
≤
n
≤
24
)
n(1 \leq n\leq 24)
n(1≤n≤24)。
输出格式
一个整数，能拼成的不同等式的数目。
样例 #1
样例输入 #1
14
样例输出 #1
2
样例 #2
样例输入 #2
18
样例输出 #2
9
提示
【输入输出样例 1 解释】
2
2
2 个等式为
0
+
1
=
1
0+1=1
0+1=1 和
1
+
0
=
1
1+0=1
1+0=1。
【输入输出样例 2 解释】
9
9
9 个等式为
0
+
4
=
4
0+4=4
0+4=4、
0
+
11
=
11
0+11=11
0+11=11、
1
+
10
=
11
1+10=11
1+10=11、
2
+
2
=
4
2+2=4
2+2=4、
2
+
7
=
9
2+7=9
2+7=9、
4
+
0
=
4
4+0=4
4+0=4、
7
+
2
=
9
7+2=9
7+2=9、
10
+
1
=
11
10+1=11
10+1=11、
11
+
0
=
11
11+0=11
11+0=11。
原题回顾 END
🟢详解🟢
不够完美的AC代码
#include
using namespace std;
const int N = 1000;
int n;
int fire[10]={6,2,5,5,4,5,6,3,7,6}; //一一对应的火柴数
int arr[4]; //存储等式中的三个数字A B C
int res; //方案数
int cal(int num) //数组中没有的，使用已有数据计算
{
int add_sum=0;
if(num<10) return fire[num];
else
{
while(num){
add_sum+=fire[(num%10)];
num/=10;
}
return add_sum;
}
}
void dfs(int x,int sum) //A+B=C中 x=1,2,3 分别对应A,B,C sum是使用火柴数
{
//剪枝
if(sum>n) return ;
if(x>3){
if(sum==n && arr[1]+arr[2]==arr[3]){ //同时满足题中两个条件1、给定火柴数 2、等式成立
res++;
}
return ;
}
for(int i=0;i<=N;i++){ //普普通通搜一搜
arr[x]=i;
dfs(x+1,sum+cal(i)); //此处调用cal函数
arr[x]=0;
}
}
int main(){
cin >> n;
n=n-4;
dfs(1,0);
printf("%d",res);
return 0;
}
洛谷评测
优化
注意到10以上的fire可能会大量的重复用到，故可把cal递归方式改为递推，并且使用数组存储
#include
using namespace std;
const int N = 1000;
int n;
int fire[N]={6,2,5,5,4,5,6,3,7,6}; //一一对应的火柴数
int arr[4]; //存储等式中的三个数字A B C
int res; //方案数
void dfs(int x,int sum) //A+B=C中 x=1,2,3 分别对应A,B,C sum是使用火柴数
{
//剪枝
if(sum>n) return ;
if(x>3){
if(sum==n && arr[1]+arr[2]==arr[3]){ //同时满足题中两个条件1、给定火柴数 2、等式成立
res++;
}
return ;
}
for(int i=0;i<N;i++){ //普普通通搜一搜
arr[x]=i;
dfs(x+1,sum+fire[i]); //此处直接使用数组数据
arr[x]=0;
}
}
int main(){
cin >> n;
n=n-4;
for(int i=10;i<N;i++){
fire[i]=fire[i/10]+fire[i%10];
}
dfs(1,0);
printf("%d",res);
return 0;
}
洛谷评测
对于测试样例 优化后代码效率提高了一倍左右
若还想优化，可以试着卡
N
N
N的范围，不过有一定的风险，可能会漏可行解。（实际上N可以卡到600）
此题完结😊
—D 题 详 解—
🟢原题回顾🟢
📋D 洛谷-P1219 [USACO1.5] 八皇后 Checker Challenge
Label 暴力搜索 Level 普及/提高-
[USACO1.5] 八皇后 Checker Challenge
题目描述
一个如下的
6
×
6
6 \times 6
6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列
2
4
6
1
3
5
2\ 4\ 6\ 1\ 3\ 5
2 4 6 1 3 5 来描述，第
i
i
i 个数字表示在第
i
i
i 行的相应位置有一个棋子，如下：
行号
1
2
3
4
5
6
1\ 2\ 3\ 4\ 5\ 6
1 2 3 4 5 6
列号
2
4
6
1
3
5
2\ 4\ 6\ 1\ 3\ 5
2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前
3
3
3 个解。最后一行是解的总个数。
输入格式
一行一个正整数
n
n
n，表示棋盘是
n
×
n
n \times n
n×n 大小的。
输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
样例 #1
样例输入 #1
6
样例输出 #1
2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4
提示
【数据范围】
对于
100
%
100\%
100% 的数据，
6
≤
n
≤
13
6 \le n \le 13
6≤n≤13。
原题回顾 END
🟢AC代码🟢
还是比较简单的，就直接放代码了😊
#include
using namespace std;
const int N = 15;
int n; //矩阵规模
int arr[N]; //记录摆放位置
bool st[N],lst[2*N-1],rst[2*N-1]; //列 左与右
int res;
void dfs(int x)
{
if(x>n){
res++;
if(res<4){
for(int i=1;i<=n;i++){
cout << arr[i] << ' ';
}
cout << '\n';
}
return ;
}
for(int i=1;i<=n;i++){
if(!st[i]&&!lst[i+x]&&!rst[i-x]){
st[i]=true;
lst[i+x]=true;
rst[i-x]=true;
arr[x]=i;
dfs(x+1);
st[i]=false;
lst[i+x]=false;
rst[i-x]=false;
arr[x]=0;
}
}
}
int main()
{
cin >> n;
dfs(1);
cout << res;
return 0;
}
或许还能优化下🤞
小声哔哔
刚接触八皇后问题的同学可以参考下知名vup@木子喵neko 的视频教程喵~
哔哩哔哩 -【neko算法课】DFS与BFS【5期】
🟪感谢阅读喵 关注作者谢谢喵~💕
本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/fd7e77341f.html
相关推荐
-
Java清览题库实验 (实验二 ~ 实验六)
文章目录 实验二 基本数据类型、控制语句的应用 （5） 两个数之间的经典问题 谷值 找出n以内的所有”孪生数”. 完数 完数（三个） 实验三 类与对象 (3…
-
微信小程序-JAVA Springboot项目-后端搭建-项目搭建02
目录 一、序言 二、后端搭建 三、最终效果 一、序言 本文主要讲述一个微信小程序前后端项目搭建的过程，主要内容包括小程序（前端）搭建和后端搭建，其中会描述可能遇到的…
-
Java使用MD5加盐对密码进行加密处理,附注册和登录加密解密处理
前言 在开发的时候，有一些敏感信息是不能直接通过明白直接保存到数据库的。最经典的就是密码了。如果直接把密码以明文的形式入库，不仅会泄露用户的隐私，对系统也是极其的不厉，这样做是非常…
-
工具篇–SpringBoot与SpringCloud 的版本对应关系&SpringBoot与JDK对应关系（官网文档解释）
文章目录 前言 一、SpringCloud 与SpringBoot 版本对应关系： 1. 1 进入 SpringCloud 官网 1. 2 关系对应： 1. 3 SpringClo…
-
基于Jenkins CICD的代码发布与回滚 Jenkins+Git+Docker 发布 Java 项目 Jenkins+Git+Ansible 发布PHP 项目
目录 案例概述 案例环境 基于 Jenkins+Git+Docker 发布 Java 项目 1、配置 Git 仓库 2、配置 Docker服务器 3、部署镜像仓库 5、配置Jenk…
-
万字长文，链表排序算法——冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序、基数排序精讲及python实现
1. 链表排序简介 在数组排序中，常见的排序算法有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。 而对于链表排序而言，因为链表…
-
适合小白学习的GAN（生成对抗网络）算法超详细解读
前言 “GANs are ‘the coolest idea in deep learning in the last 20 years.’ ”̵…
-
数据结构-单链表
1 链表的概念及结构 概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 从以上图片可以看出： 1.链式结构在逻辑上是…
-
插入排序（一）——直接插入排序与希尔排序
目录 一.前言 二.排序的概念及其运用 1.1排序的概念 1.2 常用排序算法 三.常用排序算法的实现 3.1 插入排序 3.1.1 基本思想 3.1.2 直接插入排序 3.1.3…
-
深度优先搜索(DFS)算法
目录 算法思想 时间复杂度和空间复杂度 算法实现 算法优缺点 应用领域 算法思想 深度优先搜索（DFS）算法的思想是从图的某个起始顶点开始，沿着一条路径尽可能深入地访问图中的所有顶…
