《啊哈算法》第四章之深度优先搜索
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
✌好听的歌一起分享
目录
模板
关于dfs先来个模板它分为遍历和边界两部分
模板不是万能的它只是一种思路
void dfs(int step)
{for(遍历每一种可能) {
......
book[i] = 1;(标记)
dfs(step + 1);(递归)
book[i] = 0;(取消标记)
}
if(判断边界) {
......
return;(返回上一步)
}
}
一个if判断边界判断后还要return到最近调用的地方
一个for用来遍历遍历后还要标记递归取消标记
例子
1关于遍历
对比几个例子从对比中加深对dfs模板的理解
for(int i = 0; i < 20; ++i)//一个for遍历20个队员
if(book[i] == 0)//如果他没被访问
{
book[i] = 1;//标记
dfs(index+1, sum+a[i][index]);//递归
book[i] = 0;//取消标记
}for(int i = 1; i <= n; ++i)
if(book[i] == 0) { //数字i没放入
a[place] = i; //把i放入第place个盒子
book[i] = 1; //标记
dfs(place + 1); //递归下一个盒子
book[i] = 0; //取消标记
}for(int i = 1; i <= 9; ++i)
if(book[i] == 0) {//数字i未被选中
a[place] = i; //扑克i放入第place号盒子
book[i] = 1; //标记
dfs(place + 1); //递归
book[i] = 0; //取消标记
}2关于边界
if(index == 6)//一个if判断边界
{
max_score = max(max_score, sum);
return; //返回上一步
//return不能去掉
}if(place == n + 1) {//到达最后一个盒子的下一个
ans++; //总共的可能
for(int i = 1; i <= n; ++i)
cout<<a[i];
cout<<endl;
return; //返回上一个盒子最近一次调用dfs的地方
//return可去
}if(place == 10) { //来到不存在的第10个盒子已结束
if(a[1]*100+a[2]*10+a[3] + a[4]*100+a[5]*10+a[6] == a[7]*100+a[8]*10+a[9]) {
ans++;
printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],
a[4],a[5],a[6],a[7],a[8],a[9]);
}
return; //返回上一个盒子
//这里return可去掉输出不变
}正文
1概念
理解递归的前提是理解递归😀
这些简单的例子核心代码不超过20行却饱含深度优先搜索Depth First Search, DFS的基本模型。
理解深度优先搜索的关键在于解决“当下该如何做”。
至于“下一步如何做”则与“当下该如何做”是一样的。
比如我们写的dfs(step)函数的主要功能就是解决当你在第step个盒子的时候你该怎么办。
通常的方法就是把每一种可能都去尝试一遍一般用for循环来遍历。
当前这一步解决后便进入下一步dfs(dfs + 1)。
下一步的解决方法和当前这步解决方法是完全一样的
再看个递归路线图
1、访问顶点a
2、依次从a的未被访问的邻接点出发对图进行深度优先遍历直至图中所有和a有路径相通的顶点被访问💪
3、若此时图中尚有顶点未被访问则从一个未被访问的顶点出发重新进行深度优先遍历直到图中所有顶点均被访问过为止
路径
a b d h d b e i e j e b a c f k f c g橙色表示初次经过
过程描述
第一条路访问了a,b,d,h走到底了就从h退回(1)d发现节点d没有除h以外的没访问过的就退回(2)bb有除d以外未访问过的e所以又从e开始进行dfs...
被访问的顺序
a --> b --> d --> h --> e --> i --> j --> c --> f --> k --> g
2解救小哈
题目
1有一天我的女朋友一个人去玩迷宫因为方向感很差迷路了我得知后马上去解救她
2迷宫由m行n列的单元格组成m和n都小于100每个单元格要么是空地要么是障碍
3我的任务是帮助女朋友找到一条从迷宫起点通向女朋友位置的最短路径
4注意障碍是不能走的也不能走到迷宫外
思路
开始套模板吧
1首先我们用一个二维数组a存储这个迷宫
2假设一开始我在迷宫入口处11女朋友在p, q就要找11到pq的最短路径
3一开始只能往右或下走到底往哪个方向走呢只能一个一个方向尝试
4于是我们建立一个方向数组使用循环很容易得到下一步坐标
int next[4][2] = { //方向数组循环得到下一步坐标
{-1,0}, //上
{1, 0}, //下
{0,-1}, //左
{0, 1}};//右遍历所有点怎么遍历呢
int tx, ty; //作为临时变量
for(int i = 0; i < 4; ++i) {
tx = x + next[i][0];
ty = y + next[i][1];
}接下来还需要补充遍历的内容
1判断是否超出迷宫范围
2判断到达的地方是否是空地且没有走过
int tx, ty; //作为临时变量
for(int i = 0; i < 4; ++i) {
tx = x + next[i][0];
ty = y + next[i][1];
//判断越界
if(tx < 1 || ty < 1 || tx > m || ty > n)
continue; //跳出本次循环
//空地且未走过
if(a[tx][ty] == 0 && book[tx][ty] == 0) {
book[tx][ty] = 1; //标记
dfs(tx, ty, step + 1); //递归
book[tx][ty] = 0; //取消标记
}
}接下来需要判断边界也就是是否到达了女朋友那里我们用ans保留当前最短路径
//判断边界本题为小哈位置
if(x == p && y == q) {
ans = min(ans, step);
return; //返回上一步
}完整代码
#include<iostream>
using namespace std;
int a[100][100], book[100][100], ans = 6666666;
int p, q; //小哈坐标
int m, n; //迷宫的行列
void dfs(int x, int y, int step)
{
int next[4][2] = { //方向数组循环得到下一步坐标
{-1,0}, //上
{1, 0}, //下
{0,-1}, //左
{0, 1}};//右
//枚举四种走法
int tx, ty; //作为临时变量
for(int i = 0; i < 4; ++i) {
tx = x + next[i][0];
ty = y + next[i][1];
//判断越界
if(tx < 1 || ty < 1 || tx > m || ty > n)
continue; //跳出本次循环
//空地且未走过
if(a[tx][ty] == 0 && book[tx][ty] == 0) {
book[tx][ty] = 1; //标记
dfs(tx, ty, step + 1); //递归
book[tx][ty] = 0; //取消标记
}
}
//判断边界本题为小哈位置
if(x == p && y == q) {
ans = min(ans, step);
return; //返回上一步
}
}
int main()
{
int startx, starty; //初始位置坐标
cin>>m>>n;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
cin>>a[i][j];
cin>>startx>>starty>>p>>q;
book[startx][starty] = 1; //标记初始已走过
dfs(startx, starty, 0);
cout<<ans;
return 0;
}
5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3
7原方案通过二维数组book记录在迷宫中走过的点迷宫越大book数组占的空间越大
下面是在原代码基础上的优化优化方法如下
将到达过的点在二维数组a中位置的值改为-1未到达的点依然为0障碍依然为1容易区分且占用内存少
优化代码
#include<iostream>
using namespace std;
int a[100][100], ans = 6666666;
int p, q; //小哈坐标
int m, n; //迷宫的行列
void dfs(int x, int y, int step)
{
int next[4][2] = { //方向数组循环得到下一步坐标
{-1,0}, //上
{1, 0}, //下
{0,-1}, //左
{0, 1}};//右
//枚举四种走法
int tx, ty; //作为临时变量
for(int i = 0; i < 4; ++i) {
tx = x + next[i][0];
ty = y + next[i][1];
//判断越界
if(tx < 1 || ty < 1 || tx > m || ty > n)
continue; //跳出本次循环
//空地且未走过
if(a[tx][ty] == 0) {
a[tx][ty] = -1; //标记走过
dfs(tx, ty, step + 1); //递归
a[tx][ty] = 0; //取消标记
}
}
//判断边界本题为小哈位置
if(x == p && y == q) {
ans = min(ans, step);
return; //返回上一步
}
}
int main()
{
int startx, starty; //初始位置坐标
cin>>m>>n;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
cin>>a[i][j];
cin>>startx>>starty>>p>>q;
a[startx][starty] = -1; //标记初始已走过
dfs(startx, starty, 0);
cout<<ans;
return 0;
}
仔细观察 我们只修改了
第2行去掉了全局变量book数组的声明
第2325行标记走过和未走过时book改为a赋值从1变成-1
第42行初始标记走过从book[startx][starty] = 1改为a[startx][starty] = -1
-----------------------------------------------------------------------------------------------------------
例子源码和题目
其中12可以去掉if判断边界中的return3不能去掉关于为什么我猜是3中dfs递归时存在两个变量
1小学奥数
□□□ + □□□ = □□□
将数字1 ~ 9分别填入 □ 种每个数字只能使用一次使等式成立
比如173 + 286 = 459 与 286 + 173 = 459 为一种可能
#include<iostream>
#include<cstdio> //printf()
using namespace std;
int a[10], book[10], ans = 0; //全局变量
void dfs(int place)
{
for(int i = 1; i <= 9; ++i) {
if(book[i] == 0) {//数字i未被选中
a[place] = i; //扑克i放入第place号盒子
book[i] = 1; //标记
dfs(place + 1); //递归
book[i] = 0; //取消标记
}
}
if(place == 10) { //来到不存在的第10个盒子已结束
if(a[1]*100+a[2]*10+a[3] + a[4]*100+a[5]*10+a[6]
== a[7]*100+a[8]*10+a[9]) {
ans++;
printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],
a[4],a[5],a[6],a[7],a[8],a[9]);
}
return; //返回上一个盒子
//这里return可去掉输出不变
}
}
int main()
{
dfs(1); //从第一个盒子开始
cout<<ans / 2<<endl;
return 0;
}
......(一共336行所以是168种可能)
748+215=963
752+184=936
754+182=936
762+183=945
763+182=945
782+154=936
782+163=945
783+162=945
784+152=936
1682全排列
小哼要将编号为12......n的n张扑克放到编号为12......n的n个盒子里每个盒子有且只能放一张扑克问一共有多少种不同放法全排列n <= 9
#include<iostream>
using namespace std;
int a[10], book[10], n, ans = 0;
void dfs(int place)
{
for(int i = 1; i <= n; ++i) {
if(book[i] == 0) { //数字i没放入
a[place] = i; //把i放入第place个盒子
book[i] = 1; //标记
dfs(place + 1); //递归下一个盒子
book[i] = 0; //取消标记
}
}
if(place == n + 1) {//到达最后一个盒子的下一个
ans++; //总共的可能
for(int i = 1; i <= n; ++i)
cout<<a[i];
cout<<endl;
return; //返回上一个盒子最近一次调用dfs的地方
//return可去
}
}
int main()
{
cin>>n;
dfs(1); //从第一个盒子开始
cout<<ans<<endl;
return 0;
}
3
123
132
213
231
312
321
64的话有24种5的话有120种....
3组队
2019蓝桥杯C/C++B组ヽ(✿ﾟ▽ﾟ)ノ
作为篮球队教练你需要从以下名单中选出 1 号位至 5 号位各一名球员
组成球队的5人首发阵容。
每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1
号位至 5 号位的评分之和最大可能是多少
#include<iostream>
using namespace std;
int book[20], max_score = 0;
int a[20][6] = //声明初始化二维数组存储表格数据
{
{1,97,90,0,0,0},
{2,92,85,96,0,0},
{3,0,0,0,0,93},
{4,0,0,0,80,86},
{5,89,83,97,0,0},
{6,82,86,0,0,0},
{7,0,0,0,87,90},
{8,0,97,96,0,0},
{9,0,0,89,0,0},
{10,95,99,0,0,0},
{11,0,0,96,97,0},
{12,0,0,0,93,98},
{13,94,91,0,0,0},
{14,0,83,87,0,0},
{15,0,0,98,97,98},
{16,0,0,0,93,86},
{17,98,83,99,98,81},
{18,93,87,92,96,98},
{19,0,0,0,89,92},
{20,0,99,96,95,81}
};
//index表示当前位置, sum是当前组合总分
void dfs(int index, int sum)
{
if(index == 6)//一个if判断编辑
{
max_score = max(max_score, sum);
return; //返回上一步
//return不能去掉
}
for(int i = 0; i < 20; i++)//一个for遍历20个队员
if(book[i] == 0)//如果他没被访问
{
book[i] = 1;//标记
dfs(index+1, sum+a[i][index]);//递归
book[i] = 0;//取消标记
}
}
int main()
{
dfs(1, 0); //第一个成员开始总分为0
cout<<max_score<<endl;
return 0;
}
490--------------------------------------------------------------------------------------
递归中的return
1C++ 递归函数中的return是指
从被调用函数返回到主调函数中继续执行并非一遇到return整个递归结束
2return 语句顾名思义是终止当前正在执行的函数并将控制权返回到调用该函数的地方
3在void的函数中也可以多次使用return功能和循环中的break一样在中间位置提前退出正在执行函数也就是回到原来位置执行下一行代码
4return; 表示结束本次函数
5⭐递归中的return常用来作为递归终止的条件当达到递归终止条件时首先return的是最底层调用的函数return之后继续执行上一层调用该函数之后的代码⭐
在我对return进行理解时这篇200收藏的文章给了我一定启发关于递归中return的理解最浅显易懂_Pledgee的博客-CSDN博客_递归函数return怎么理解
--------------------------------------------------------------------------------------
dfs中隐式return
隐式return的情况是执行完函数后自动返回上一级
1走方格
题目
给定一个m*n方格阵沿着方格边线走从左上角(0, 0)开始每次只能往右或往下走一个单位距离问走到右下角m, n一共有多少种不同走法
输入
一行包含两个整数 m 和 n (m >= 1 && m <= 10) && (n >= 1 && n <= 10)
输出
输出一个整数表示走法数量
解析
代码
#include<iostream>
using namespace std;
int m, n, num = 0;
int dfs(int x, int y)
{
if(x == m && y == n)
num++;//走法数量+1
else
{
if(x < m)
dfs(x + 1, y);//递归行加一
if(y < n)
dfs(x, y + 1);//递归列加一
}
}
int main()
{
while(cin>>m>>n)
{
dfs(0, 0);
cout<<num<<endl;
num = 0;
}
return 0;
}3 2
10
5 5
252
10 10
1847562例子2
例子2只为说明隐式return不需要return的情况
#include <iostream>
using namespace std;
void dfs(int n)
{
cout << "level: " << n << endl;/*1*/
if (n < 4)
dfs(n + 1);
cout << "level: " << n << endl;/*2*/
}
int main()
{
dfs(1);
return 0;
}输出
lever: 1执行/*1*/
lever: 2执行/*1*/
lever: 3执行/*1*/
lever: 4执行/*1*/
lever: 4执行完/*2*/后函数返回上一级dfs递归的下一行
lever: 3同上
lever: 2同上
lever: 1同上
level: 1
level: 2
level: 3
level: 4
level: 4
level: 3
level: 2
level: 1