acwing算法笔记-搜索

DFS 与 BFS 的区别

搜索方法 数据结构 空间复杂度 性质
DFS stack $O(h)$ 不具有最短性
BFS queue $O(2^h)$ 最短路径

DFS

  1. DFS 俗称爆搜，其中最重要的就是搜索顺序
  2. DFS 搜索到叶节点后，就会回溯到发生分支的地方，注意回溯后要恢复现场
  3. DFS 有的时候会剪枝优化，剪枝大致有两种，一种是最优化剪枝，一种是可行性剪枝（八皇后问题）

回溯角度DFS

DFS一般有两种角度，一种是回溯角度DFS，也就是搜索所有的分支，这种就是回溯类的题目，但其实本质还是DFS
然后分析流程如下

  1. 首先确定搜索顺序，例如按位，按行，按列等等
  2. 然后写DFS函数，确定参数和返回值，返回值的确定取决于我们每一层想要存什么；参数取决于每一层需要什么信息
    其中参数的写法不固定，可以有很多种写法，这里我们固定写法。对于输入我们直接作为引用放入DFS参数（类似全局变量的效果）
    然后搜索位置和对于当前分支的变量 我们当作局部变量放入DFS参数，这样就可以达到自动回溯的效果
    然后是否恢复现场取决于回溯到当前层时，你想要的情况是什么

842. 排列数字

基本思路

DFS主要就是明确搜索的顺序，这题搜索的顺序很简单，直接按位搜索即可。

DFS参数，回溯，恢复现场的本质：

  1. DFS其实就是递归搜索树，层层进入，层层回溯
  2. 如果变量在DFS的参数里，那么变量会跟着一起回溯，是系统栈帮我们自动回溯的
  3. 如果变量不在DFS的参数里，那么当然变量就不会自动回溯了，所以如果你需要回溯的话，可以自己手动回溯
  4. 恢复现场实际就是 变量 回溯到当前层的时候 变量 要恢复到当前层未修改时的状态
    所以是否恢复现场就取决于 你是否想让当前层恢复到未修改时的状态
    经验之谈：外部搜索（多个分支）需要恢复现场 内部搜索（单个分支）不需要恢复现场
  5. 变量恢复现场 要满足两点 1. 变量需要回溯到当前层 2. 当前层最终变量没有修改 手动回溯一定满足这两点，自动回溯可能不满足第二点

以全排列为例分析，首先明确全排列问题，搜多个分支，为了防止污染其他分支，肯定是要恢复现场的

  1. 版本1，state没有作为DFS的参数，肯定是要手动回溯的，满足恢复现场
  2. 版本2，state还是没有作为DFS的参数，只是进行了状态压缩，和版本1一样，需要手动回溯，满足恢复现场
  3. 版本3，state作为DFS的参数，自动回溯了，并且当前层state没有改变，满足恢复现场
  4. 版本4，state作为DFS的参数，自动回溯了，但是当前层的state改变了，所以自动回溯无法恢复现场，所以还是手动回溯恢复现场

参考代码

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
// 1. 最直接版本
#include <iostream>
using namespace std;

const int N = 10;

int n;
int path[N];   //保存方案
bool st[N];    //状态数组

void dfs(int u)  //u代表DFS的当前层的信息 位置
{
    if(u == n)    //递归边界
    {
        for(int i=0; i<n; i++) cout << path[i] << ' ';   //输出当前方案
        puts("");
        return;
    }

    for(int i=1; i<=n; i++)    //当前位可以填哪些数
    {
        if(!st[i])             //没有被用过的数
        {
            path[u] = i;
            st[i] = true;      //i被用过
            dfs(u+1);          //DFS进入下一层      
            st[i] = false;     //手动回溯 恢复现场
            //这里path不需要手动回溯，因为其他分支可以完全覆盖它
        }
    }
}

int main()
{
    cin >> n;

    dfs(0);

    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
// 2. 状态压缩
#include <iostream>

using namespace std;

const int N = 10;
int n;
int path[N];
int state;

void dfs (int u) {
    if (u == n) {
        for (int i = 0; i < n; ++ i) cout << path[i] << ' ';
        cout << endl;
        return;
    }


    for (int i = 1; i <= n; ++ i) {

        if (!(state >> i & 1)) {
            path[u] = i;
            state += (1 << i);  //当前层的状态改变了
            dfs(u + 1);
            state -=(1 << i);  //手动回溯 恢复现场
        }
    }
}

int main () {
    cin >> n;
    dfs(0);
    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
// 3. 状态压缩 + state 局部变量
#include <iostream>

using namespace std;

const int N = 10;
int n;
int path[N];

void dfs (int u, int state) {
    if (u == n) {
        for (int i = 0; i < n; ++ i) cout << path[i] << ' ';
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; ++ i) {   //当前位可以填哪些数
        //状态压缩优化空间
        if (!(state >> i & 1)) {
            path[u] = i;
            dfs(u + 1, state + (1 << i));
            //我们在每层里面没有修改过state，自动回溯就可以满足恢复现场
        }
    }
}

int main () {
    cin >> n;
    dfs(0, 0);
    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
// 4. 状态压缩 + state局部变量
#include <iostream>

using namespace std;

const int N = 10;
int n;
int path[N];

void dfs (int u, int state) {
    if (u == n) {
        for (int i = 0; i < n; ++ i) cout << path[i] << ' ';
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; ++ i) {  
        if (!(state >> i & 1)) {
            path[u] = i;
            state += (1 << i);
            dfs(u + 1, state);
            state -= (1 << i);
            //因为在每层里面我们还是修改过state，自动回溯后还是不满足，所以自己手动回溯
        }
    }
}

int main () {
    cin >> n;
    dfs(0, 0);
    return 0;
}

Reference

[1]. yxc
[2]. AcWing 842. 排列数字–深度优先遍历代码+注释
[3]. AcWing 842. 排列数字—本文主要阐述代码中递归的思想！
[4]. Bug-Free 位运算代码


843. n-皇后问题

基本思路

DFS问题，主要是明确搜索顺序，N皇后问题这里有两种常见的搜索顺序

  1. 搜索行，然后可行性剪枝（列 + 两个对角线） //效率更高
  2. 搜索格子，然后可行性剪枝（行 + 列 + 两个对角线）

参考代码

思路1

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
//按位置搜索，所以搜索树的层存的是位置信息，每个位置可以放皇后或者不放皇后 两分支
//显然为了区别dfs函数是否放皇后，我们加了s参数，代表皇后的数量
#include <iostream>

using namespace std;

const int N = 10;

int n;
bool row[N], col[N], dg[N * 2], udg[N * 2];  //多个状态数组进行可行性剪枝
char g[N][N];  //存储图 = 存储方案 这里的方案是一张图

void dfs(int x, int y, int s)
{
    if (s > n) return;    //可行性剪枝
    if (y == n) y = 0, x ++ ;  //当列坐标越界，跳转到下一行的首位

    if (x == n)   //递归边界， 所有行都搜索完
    {
        if (s == n)  //皇后数量满足要求
        {
            for (int i = 0; i < n; i ++ ) puts(g[i]);  //输出答案
            puts("");
        }
        return;  //注意这个return一定要在外面，如果在里面某些分支永远到不了边界，最后会tle
    }

    g[x][y] = '.';  //初始化当前格子
    dfs(x, y + 1, s);  //不放皇后

    //放皇后 利用状态数组进行可行性剪枝
    //没有把状态放入dfs参数中，所以需要手动回溯
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        g[x][y] = 'Q';
        dfs(x, y + 1, s + 1);
        g[x][y] = '.';   //注意这里的图需要手动回溯，因为它不会被其他的分支完全覆盖，所以需要回溯到原始状态
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    }
}

int main()
{
    cin >> n;

    dfs(0, 0, 0);

    return 0;
}

思路2

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
//按行搜索，所以搜索树的层存的是行信息，每一行必然会放一个皇后
//看是在当前行的哪一列放皇后 n分支
#include <iostream>

using namespace std;

const int N = 20;   //防止对角线下标越界

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u)
{
    if (u == n)  //递归边界，所有行都搜索完
    {
        for (int i = 0; i < n; i ++ ) puts(g[i]);
        puts("");
        return;
    }

    for (int i = 0; i < n; i ++ )  //每一行必然会放一个皇后，所以直接枚举列（n分支）然后利用状态数组进行可行性剪枝
        if (!col[i] && !dg[u + i] && !udg[n - u + i])
        {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
}

int main()
{
    cin >> n;
    //提前初始化
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0);

    return 0;
}

Reference

[1]. yxc
[2]. n-皇后问题 （图解 + 朴素+剪枝） 看这一篇就够了
[3]. bug free 对角线
[4]. 状态压缩版本
[5]. 评论区解答


DFS之连通性模型

1112. 迷宫

基本思路

很经典的DFS连通性问题，由于这里只需要判断是否存在合法方案，而不是找出所有方案，所以DFS和BFS其实都是可以做的
这里我们用DFS因为DFS的代码更简短，但还是要根据数据范围判断是否有爆栈的风险

这里着重说一下恢复现场的问题，内部搜索不需要恢复现场，外部搜索需要恢复现场，连通性问题都是内部搜索问题。
个人理解内部搜索相当于是搜到一条合法分支，但是外部搜索就是需要搜到合法的所有的合法分支。
Reference里会有更多不同的理解

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
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
char g[N][N];       //存储方案
int xa, ya, xb, yb; //两点坐标  
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};   //方向向量
bool st[N][N];  //标记状态

bool dfs(int x, int y)
{
    if (g[x][y] == '#') return false;    //如果该点为障碍物，退出
    if (x == xb && y == yb) return true; //当起点坐标等于终点坐标，返回true

    st[x][y] = true;                     //标记当前点已经走过

    for (int i = 0; i < 4; i ++ )        //从x,y点开始遍历四个方向
    {
        int a = x + dx[i], b = y + dy[i];   
        if (a < 0 || a >= n || b < 0 || b >= n) continue;   //新坐标是否在地图内
        if (st[a][b]) continue;                             //新坐标已经走过
        if (dfs(a, b)) return true;                         
    }

    return false;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
        scanf("%d%d%d%d", &xa, &ya, &xb, &yb);

        memset(st, 0, sizeof st);   //一共有k个地图，所以每次都要初始化标记数组
        if (dfs(xa, ya)) puts("YES");
        else puts("NO");
    }

    return 0;
}

Reference

[1]. 迷宫DFS + BFS（附带注释
[2]. if(dfs(a, b))的解释


1113. 红与黑

基本思路

DFS连通性问题，唯一的区别就是DFS的返回值需要注意一下。

参考代码

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
#include <iostream> 
#include <cstring>

using namespace std;

const int N = 25;

int n, m;

char g[N][N];
bool st[N][N];

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int dfs (int x, int y) {
    int cnt = 1;
    
    st[x][y] = true;
    
    for (int i = 0; i < 4; i++ ) {
        int a = x + dx[i], b = y + dy[i];
        if (st[a][b]) continue;
        if (a < 0 || a > n - 1 || b < 0 || b > m - 1) continue;
        if (g[a][b] == '#') continue;
        cnt += dfs(a, b);
    }
    
    return cnt;
}

int main() {
    while (cin >> m >> n, n || m) {     //输入及停止条件，注意m,n的顺序 其中m是列，n是行
        for (int i = 0; i < n; i++ ) cin >> g[i];
        
        int x = 0, y = 0;
        for (int i = 0; i < n; i++ )
            for (int j = 0; j < m; j++ )
                if (g[i][j] == '@') x = i, y = j;   //找到DFS的起点
        
        memset(st, 0, sizeof st);
        cout << dfs(x, y) << endl;
    }
}

Reference

[1]. 红与黑
[2]. yxc代码


DFS之搜索顺序

1116. 马走日

基本思路

这里通过递归来更深刻的认识一下回溯和函数栈：
首先递归函数会不断的调用自己，其实也就是不断地进入问题，相当于是从外部层层进入内部，这在代码里其实是比较好清晰的，也就是递归函数的写法（怎么层层进入）
而回溯是函数f()从内部完成后跳出到外部到的过程，相当于是从内部层层跳出到外部，在代码里不是很能体现出来，但的确是进行了回溯。那么进入从外到内，跳出从内到外，是不是突然发现和一个数据结构很匹配，没错就是栈
这里我们 通过递归函数 使用了隐式的函数栈完成了进入和回溯的过程，这也是为什么涉及到递归的代码简短的原因。

然后关于恢复现场在这里有了更深刻的认识：其实主要就是看搜索元素是否会互相影响
连通性问题，搜索元素是点，点和点直接不会影响，因为每个点只会走一次，所以不需要恢复现场 //外部多表现为搜一个分支
现在这道题，搜索元素是路径，路径之间可能有交叉受到影响，所以需要恢复现场 //外部多表现为搜多个分支

主要就是注意日的方向有8个，其他的比较容易分析

参考代码

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
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;

int n, m;
bool st[N][N];
int ans;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};   //方向数组 
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void dfs(int x, int y, int cnt)     //cnt记录当前走了几个格子
{
    if (cnt == n * m)
    {
        ans ++ ;
        return;
    }
    st[x][y] = true;    //标记

    for (int i = 0; i < 8; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (st[a][b]) continue;
        dfs(a, b, cnt + 1);
    }

    st[x][y] = false;   //恢复现场，哪里标记，哪里恢复
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        int x, y;
        scanf("%d%d%d%d", &n, &m, &x, &y);

        memset(st, 0, sizeof st);
        ans = 0;
        dfs(x, y, 1);   //因为递归的时候已经有一个点填进去了，因该赋值为1才对

        printf("%d\n", ans);
    }

    return 0;
}

Reference

[1]. yingzhaoyang
[2]. yxc


1117. 单词接龙

基本思路

这里就是要明确搜索顺序，也就是存在公共前后缀的时候才可以往下搜索。

参考代码

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
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 21;

int n;
string word[N];
int g[N][N];//代表编号i的可以被j拼接  如i：asd，j：sdf，拼接长度为最小值g[i][j] = 2，i从0开始记位
int used[N];//编号为i的单词使用次数
int ans;

void dfs(string dragon, int last) 
{
    ans = max((int) dragon.size(), ans);//取最大值，dragon.size()为当前合并的长度

    used[last]++;//编号为last的单词被用次数++；

    for (int i = 0; i < n; i++)
        if (g[last][i] && used[i] < 2)//used[i]<2代表单词用次数不超过2
            dfs(dragon + word[i].substr(g[last][i]), i); //编号为last的可以被i拼接现在尾巴为i号

    used[last]--;//恢复现场
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> word[i];
    char start;
    cin >> start;//首字母

    for (int i = 0; i < n; i++)//遍历得到各个g[i][j]
        for (int j = 0; j < n; j++) {
            string a = word[i], b = word[j];
            for (int k = 1; k < min(a.size(), b.size()); k++)
                if (a.substr(a.size() - k, k) == b.substr(0, k)) {
                    g[i][j] = k;
                    break;
                }
        }

    for (int i = 0; i < n; i++)//找到首字母为strat的单词开始做dfs，dfs中会自动找到最大值
        if (word[i][0] == start)
            dfs(word[i], i);//从word[i]开始遍历，i代表现在是第几个单词

    cout << ans << endl;

    return 0;
}

Reference

[1]. 单词接龙(y总代码详细解析版)
[2]. tonngw
[3]. DFS 求最优解
[4]. 字符串预处理搜索


1118. 分成互质组

基本思路

此题比较有难度，直接参照大佬们的题解把，原本是最大团问题，这里数据范围不大，所以就可以利用DFS来做
[1]. tonngw
[2]. 松鼠爱葡萄
[3]. 两种解法
[4]. 分成互质组(y总代码版的保姆级注释)
[5]. 分成互质组（最简单的思路

参考代码

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
// 如何搜所有方案：按照一组一组的来搜，直到当前组不能放其他数了，再搜索下一组可以放哪些数，同时以组合的形式搜索，定一个 start
// 枚举每个数的时候，有两种选择
// 1. 把这个数加入到最后一组中
// 2. 如果不能加入，才新开一个组

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 11;

int n;
int p[N]; // 存储每个数
int group[N][N]; // 存储每个组中的数的‘下标’，最多有 N 组，每个数一组
bool st[N]; // 记录每个数是否已经被加入到其他组了
int ans = N; // 最多有 N 组，每个数一组

int gcd(int a, int b) // 欧几里得算法 求最大公约数
{
    return b ? gcd(b, a % b) : a;    
}

bool check(int group[], int gc, int i) // 判断当前数和组内所有数是否互质
{
    for (int j = 0; j < gc; j ++ )
        if (gcd(p[group[j]], p[i]) > 1) // 如果当前数 p[i] 和组内任意一个数的最大公约数大于 1 则不互质
            return false;
    return true;
}

// g：第几组，gc：组内元素个数，tc：已经搜索了多少个数了，start：组内从哪个数开始搜索（组合形式搜索防止搜索重复方案）
void dfs(int g, int gc, int tc, int start)
{
    if (g > ans) return; // 剪枝，如果当前方案组数大于 ans，那它一定不是最优，否则比答案小
    if (tc == n) ans = g; // 更新最小值

    bool flag = true; // 是否需要开新组
    for (int i = start; i < n; i ++ ) { // 搜索当前组内可以放哪些数
        if (!st[i] && check(group[g], gc, i)) { // 如果当前数没用过 且 和当前组内所有数都互质，则可以将其加入到组内
            st[i] = true;

            group[g][gc] = i; // 将当前数的下标加到组内
            dfs(g, gc + 1, tc + 1, i + 1); // 从下标 i + 1 开始继续搜索

            st[i] = false; // 回溯

            flag = false; // 可以放到当前组中，不用开新租
        }
    }

    if (flag) dfs(g + 1, 0, tc, 0); // 开一个新组，组内 0 个数，已经搜了 tc 个数了，从下标 0 开始搜
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> p[i];

    dfs(1, 0, 0, 0); // 从第 1 组开始搜索，当前组内 0 个数，总共搜索了 0 个数，从第一个数开始搜索

    cout << ans << endl;

    return 0;
}

DFS之剪枝

剪枝策略

  1. 优化搜索顺序
  2. 排除等效冗余
  3. 可行性剪枝
  4. 最优性剪枝
  5. 记忆化搜索 （实际上是DP)

165. 小猫爬山

基本思路

参照大佬们的题解看吧
[1]. Bug-Free
[2]. 代码注释齐全
[3.] 方法选择思考

参考代码

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
#include <iostream>
#include <algorithm>

using namespace std;
const int N=20;
int n,m;
int sum[N];//每辆车装的重量
int w[N];
int res=N;//最多N辆车，每人一辆
bool cmp(const int& a,const int& b) 
{
    return a>b;
}
void dfs(int u,int cnt)//当前正在安排的猫的编号为u，已经使用的车辆数量为cnt,当前这只猫的两种安排方案：插到现有的或新开一辆
{
    //最优性剪枝
    if(cnt>=res) return;//当前方案不是最优的，不用再搜了

    //边界条件,正在安排第n+1只猫，结束
    if(u==n)
    {
        res=cnt;//cnt一定小于res，因为cnt过了第一个判断条件
        return;
    }
    //方案一：插入已有的cnt车辆，编号0-cnt-1
    for(int i=0;i<cnt;i++)
    {   
        //可行性剪枝，如果坐的下的话才能坐
        if(sum[i]+w[u]<=m)
        {
            sum[i]+=w[u];
            dfs(u+1,cnt);
            sum[i]-=w[u];//恢复现场
        }
    }
    //方案二：开一辆新车,编号cnt
    sum[cnt]=w[u];
    dfs(u+1,cnt+1);
    sum[cnt]=0;//恢复现场

}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    cin>>w[i];
    //优化搜索顺序
    sort(w,w+n,cmp);//从大到小排序
    //y总写法,nb
    //sort(w,w+n);
    //reverse(w,w+n);
    dfs(0,0);//从编号为0的小猫开始安排，刚开始一辆车也没有
    cout<<res<<endl;
    return 0;
}

剪枝与优化还是比较难的，这里先留个坑以后来补！

DFS之迭代加深，双向DFS，IDA*

这个part其实比剪枝要简单，因为他们有个整体的大框架，比较好想，剪枝的话其实和DP一样，比较灵活。

迭代加深：限制搜索深度，只有失败了，才迭代加深搜索层数。
其实和BFS比较相似，区别就是迭代加深它的空间要比BFS小很多，它比较适合答案出现在浅层，但是有非常长分支的时候。

双向DFS：

对于每个部分直接看相应的题目理解算法。

170. 加成序列

基本思路

[1]. Bug-Free
[2]. tonngw

参考代码

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int path[N]; // 存储加成序列

bool dfs(int u, int depth) // u 表示当前搜索的深度以及要枚举的位置的下标，depth 表示最大搜索深度
{
    if (u > depth) return false; // 如果当前搜索深度超过了最大深度还没找到答案，直接返回 false 剪枝
    if (path[u - 1] == n) return true; // 如果序列最后一个数是 n 了说明找到了一种方案直接返回 true


    bool st[N] = {0}; // 标记 和 是否被使用过，相同的和只搜一次，保证这个分支上不搜索重复的节点，st 数组只和当前层有关，不涉及恢复现场
    // 从大到小枚举当前位置上可以填的数，且必须是前两两个数的和
    for (int i = u - 1; i >= 0; i -- )
        for (int j = i; j >= 0; j -- ) {
            int s = path[i] + path[j];
            if (s > n || s <= path[u - 1] || st[s]) continue; // 可行性剪枝 + 排除等效冗余（st[s]）

            st[s] = true;
            path[u] = s; // 将和 s 放到当前位置上（下次搜索直接覆盖就行，所以不需要恢复现场）
            if (dfs(u + 1, depth)) return true; // 搜索下一个位置上的数
            // 这里不需要 st[s] = false; 回溯，因为在当前层每个和只能用一次
        }

    return false;
}

int main()
{
    path[0] = 1; // 任何序列的第一个数都是 1，最后一个数是 n
    while (cin >> n, n) {
        int max_depth = 1; 
        while (!dfs(1, max_depth)) max_depth ++ ; // 从第 1 层开始搜下标为 1 的位置上应该填哪个数，搜不到扩大一层

        // 循环结束说明找到了答案，输出加成序列
        for (int i = 0; i < max_depth; i ++ ) cout << path[i] << ' ';
        cout << endl;
    }

    return 0;
}

171. 送礼物

基本思路

[1]. Bug-Free
[2]. 美琴
[3]. Repeater

参考代码

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 1 << 25;  // k最大是25， 因此最多可能有2^25种方案

int n, m, k;
int g[50];       // 存储所有物品的重量
int weights[N];  // weights存储能凑出来的所有的重量
int cnt = 0;
int ans;  // 用ans来记录一个全局最大值

// u表示当前枚举到哪个数了， s表示当前的和
void dfs(int u, int s)
{
    // 如果我们当前已经枚举完第k个数（下标从0开始的）了， 就把当前的s， 加到weights中去
    if (u == k) {
        weights[cnt++] = s;
        return;
    }

    // 枚举当前不选这个物品
    dfs(u + 1, s);

    // 选这个物品, 做一个可行性剪枝
    if ((LL)s + g[u] <= m) {  //计算和的时候转成long long防止溢出
        dfs(u + 1, s + g[u]);
    }
}

void dfs2(int u, int s)
{
    if (u == n) {  // 如果已经找完了n个节点， 那么需要二分一下
        int l = 0, r = cnt - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (weights[mid] <= m - s)
                l = mid;
            else
                r = mid - 1;
        }
        ans = max(ans, weights[l] + s);
        return;
    }

    // 不选择当前这个物品
    dfs2(u + 1, s);

    // 选择当前这个物品
    if ((LL)s + g[u] <= m)
        dfs2(u + 1, s + g[u]);
}

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i++)
        cin >> g[i];

    // 优化搜索顺序（从大到小）
    sort(g, g + n);
    reverse(g, g + n);

    // 把前k个物品的重量打一个表
    k = n >> 1;
    dfs(0, 0);

    // 做完之后， 把weights数组从小到大排序
    sort(weights, weights + cnt);

    // 判重
    int t = 1;
    for (int i = 1; i < cnt; i++)
        if (weights[i] != weights[i - 1])
            weights[t++] = weights[i];
    cnt = t;

    // 从k开始， 当前的和是0
    dfs2(k, 0);

    cout << ans << endl;

    return 0;
}

BFS

  1. 最短路问题一般可以用BFS
  2. DP问题是特殊的最短路问题，即没有环存在的最短路问题
  3. DFS可以保证搜到终点，但不能保证搜到的路径是最短的，所以一般要搜出所有的路径，最短路问题里就很容易超时
  4. DFS没有固定的模板，BFS有常用的模板
  5. 边权都为1的最短路问题才会用到BFS

844. 走迷宫

基本思路

BFS模板：

  1. 初始化队列
  2. while queue不为空
  3. 队顶元素出队
  4. 遍历，合法的入队

参考代码

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
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;   //定义坐标的数据结构

const int N = 110;

int n, m;
int g[N][N], d[N][N];        //g存图 d记录点的距离

int bfs()
{
    queue<PII> q;

    memset(d, -1, sizeof d);   //初始化各个点到原点的距离为-1
    d[0][0] = 0;               //原点到自己的距离为0
    q.push({0, 0});            //原点进队

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};    //定义方向向量，这里是上右下左

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )  //往四个方向走
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            //在边界内 并且是空地可以走 且之前没有走过
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;     //更新
                q.push({x, y});                         //进队
            }
        }
    }

    return d[n - 1][m - 1]; //返回右下角点的距离
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> g[i][j]; //读入地图信息

    cout << bfs() << endl;

    return 0;
}

Reference

[1]. yxc
[2]. AcWing 844. 走迷宫(C++详细注释)
[3]. 走迷宫(数组模拟，C++STL， python、打印路径)
[4]. Bug-Free


DFS相关题目

思路大方向

个人理解，DFS分为回溯角度(回溯法)和遍历角度
回溯角度：处理DFS每一层的信息（一层有多个节点）回溯角度的DFS其实就是回溯法
遍历角度：处理DFS每一个节点的信息

对于求所有的解，所有路径，所有分支，很明显应该是用回溯角度的DFS，也就是回溯法。大部分的DFS题目都是采用的回溯角度的DFS
对于遍历所有节点，搜索所有节点的一些信息，很明显应该用遍历角度的DFS，这个时候我们只是用DFS去遍历而已。常见于二叉树一些搜索问题

其中回溯角度的DFS写法很多变，因为回溯的写法可以很灵活。这里我们尽量把写法统一，便于速度和个人风格的培养。
本质就是确立DFS函数，从以下方面考虑

  1. DFS函数的意义 //明确搜索顺序，DFS的当前层的含义，通俗来讲当前层搜的是什么
  2. DFS函数的返回值 //当前层需要返回的信息，大部分都不需要返回所以返回值常为void
  3. DFS的参数 //输入和全局变量(对于所有分支)，都当作引用传进DFS函数 其余的就是局部变量(对于当前分支)，自动回溯
    然后判断还是否需要手动回溯，就是看当前层是不是我们想要的结果，如果不是就手动回溯一下

已打卡题目

LeetCode 17. 电话号码的字母组合

算法 > AcWing
#算法 #搜索
acwing算法笔记-搜索
https://vendestine.com/bfs-dfs
Author
Wenzhe Li
Posted on
April 20, 2022
Licensed under