dfs超详解（基本用法+蓝桥杯真题）

dfs
dfs即深度优先搜索（Depth first search），搜索算法中的一种，用递归进行搜索，是尽可能深的搜索每一个节点，可以理解为不撞南墙不回头。
用于解决一些树的遍历和图的遍历，由于是通过递归实现，时间复杂度较高，一般题中所给数据较小。
dfs在蓝桥杯中出现率很高，正如图中所示，无论是省赛国赛都出现了很多于dfs相关的题目，而且出现的难度会相对高一些。

如何理解dfs

对于刚接触dfs算法的人，个人感觉应该跟b站的up主画一下递归搜索树，画递归搜索树有助于理解dfs中的深度优先。例如下面的排列问题

排列问题

排序问题是dfs中比较简单的应用，主要帮助理解dfs

输入一个数字，输出其全排列（字典序） 
1

这个是对应递归搜索树（图丑轻喷），就是最开始选第一位，有1，2，3，三种选择，如果先选择1，之后选第二位有2，3，两种选择，选择2，最后第三位只能选择3，然后输出第一种排列，之后回溯回到第二位的选择，第二位选择3，第三位就选择2，输出，之后回溯到第一位选择，第一位选择2…以此类推。
就是不撞南墙不回头，撞到南墙输出一个结果，之后回到上一个位置继续撞南墙。

#include<bits/stdc++.h>
using namespace std;
int a[20];//储存数字
int book[20];//标记是否选过数，1是已选，0是未选
int n;//输入数字
void dfs(int step)
{
    if(step == n + 1)
    {
        for(int i = 1; i <= n;i++)
        {
            cout<<a[i];
        }
        cout<<endl;
        return ;
    }
    for(int i = 1; i <= n;i++)
    {
        if(book[i] == 0)
        {
        a[step] = i;
        book[i] = 1;
        dfs(step + 1);
        book[i] = 0;//回溯
        }

    }
    return ;
}
int main()
{
    cin>>n;
    dfs(1);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

由于递归十分的抽象，如果像我一样抽象思维不是很好的话，可以试着把程序在纸上跑一遍，一步一步的执行，这样会加深对dfs的理解，也可以跟着b站上边的老师把程序走一遍，下图就是我自己一步步写出的程序执行的过程（差不多写到132的时候就基本理解了，过程其实有点绕，尽量耐心一些）

对应的运行结果

迷宫问题

给出一个迷宫（n行m列），标记1是障碍，标记0可以通过

0100
0001
1100
0011
1010
1
2
3
4
5

从入口到出口
求最短路径

输入：迷宫大小出入口以及迷宫元素
输出：最短路径否则输出NO
1
2

想解决迷宫问题要先理解方向数组
方向数组
其中（x，y）并非是数学坐标系的横纵坐标，而是第x行第y列，针对于二维数组

方向数组跟正常理解的左加右减上加下减正好是反过来的，是按照数组的下标来操作的
方向数组可以写成两个一维数组也可以写成一个二维数组，按照个人的喜好选择就行

int next1[4][2]={
	    {0,1}, //向右走一步
		{1,0},//向下走一步
		{0,-1},//向左走一步
		{-1,0}};//向上走一步
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
1
2
3
4
5
6
7

    for (int i = 0; i < 4; i++) // 四个方向试探能否通过
    {
        int tx, ty;
        tx = x + next1[i][0];
        ty = y + next1[i][1];
        //tx = x + dx[i];
        //ty = y + dy[i];
1
2
3
4
5
6
7

这个for循环一共执行四次就是从四个方向依次试探能不能通过

        if (tx <= 0 || tx > n || ty <= 0 || ty > m)
        {
            continue; // 超出边界，重新试探
        }
1
2
3
4

if语句的作用是剪枝，如果超出迷宫的边界就continue（这个语句会在以后的题中出现很多次）

下边是完整代码

#include <bits/stdc++.h>
using namespace std;
int next1[4][2]={
	    {0,1}, //向右走一步
		{1,0},//向下走一步
		{0,-1},//向左走一步
		{-1,0}};//向上走一步
//int dx[4] = {0,1,0,-1};
//int dy[4] = {1,0,-1,0};
int a[100][100];   // 迷宫数组
int vis[100][100]; // 标记数组1为已经走过，0为未走过
int n, m, x, y, p, q;
int min1 = 99; // 最短路径，赋初值
void dfs(int x, int y, int step)
{
    if (x == p && y == q) //临界条件
    {
        if (step < min1)
        {
            min1 = step;
        }
        return;
    }
    for (int i = 0; i < 4; i++) // 四个方向试探能否通过
    {
        int tx, ty;
        tx = x + next1[i][0];
        ty = y + next1[i][1];
        //tx = x + dx[i];
        //ty = y + dy[i];
        if (tx <= 0 || tx > n || ty <= 0 || ty > m)
        {
            continue; // 超出边界，重新试探
        }
        if (a[tx][ty] == 0 && vis[tx][ty] == 0)
        {
            vis[tx][ty] = 1;
            dfs(tx, ty, step + 1);
            vis[tx][ty] = 0; // 回溯
        }
    }
    return;
}
int main()
{
    int sx, sy;                // 开始位置
    cin >> m >> n;             // 读入迷宫
    cin >> sx >> sy >> p >> q; // 读入入口和出口的位置
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
        }
    }
    vis[sx][sy] = 1 ;
    dfs(sx, sy, 0);
    if (min1 == 99)
    {
        cout << "NO";
    }
    else
    {
        cout << min1;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

蓝桥杯真题飞机降落

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N = 30;
int n;//飞机个数
bool st[N];//判断飞机是否降落
struct plane{
    int t,d,l;
}p[N];//表示时间Ti Di Li

//u已经有u架飞机降落
//time当前的时间，前一架飞机落地的时间
bool dfs(int u,int time)
{
    if(u >= n){
        return true;//判断边界，已下落的飞机数目大于等于飞机总数
    }
    for(int i = 0; i < n;i++)
    {
        if(!st[i])//如果飞机未下落
        {
            st[i] = true;
            if(p[i].t + p[i].d < time)//最晚下落时间小于前一架飞机降落时间
            {
                st[i] = false;//回溯
                return false;//直接返回false输出NO
            }
            int t = max(time,p[i].t) + p[i].l;//最大值函数
            if(dfs(u + 1,t))
            {
                return true;
            }
            st[i] = false;
        }
    }
    return false;
}
void solve()
{
    cin>>n;
    for(int i = 0;i < n;i++)
    {
        cin>>p[i].t>>p[i].d>>p[i].l;
    }
    if(dfs(0,0))
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
        for(int i = 0 ;i < n;i++)
    {//初始化st数组
        st[i] = false;
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //飞机降落问题
    int tl = 1;
    cin>>tl;
    while(tl--)
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

dfs的基本模板

这里给出dfs的一个模板，一部分dfs的题基本是这个模板

void dfs(int step)
{
	结束条件（特殊情况或者是输出）
	return 
	枚举可能for(int i = 1;i <= n;i++)
	dfs(step+1)
	return 
}
1
2
3
4
5
6
7
8

总结

最后说一下本文是用于自己学习的笔记以及备战蓝桥杯的笔记，如果有与其他博主相似的代码勿喷（因为我就是跟他们学的）有一些是学习到的，有一些是自己总结的，有一些的语言不是很精准也请轻喷，欢迎大家借鉴。推荐去听b站杭电刘老师的dfs基础课，里边不仅讲解dfs的基本应用也讲了一些剪枝的技巧（虽然我现在也用不太明白剪枝）。
当然会这几道题并不够学会dfs，推荐去蓝桥云课或者洛谷刷一些dfs的题目。