Htto的小站
0%

搜索

发表于 更新于 分类于 ，

[toc]

深度优先搜索

简介

DFS全称深度优先搜索，Depth First Search，是一种通用性十分强的算法，算法竞赛中的暴力流，使用计算机强大的计算能力，穷举所有情况然后逐一判断该情况是否符合要求。

棋盘连通性问题

前置知识，四连通和八连通。

  • 四连通：在四连通的条件下，两个格子相邻当且仅当它们的有相邻边。（即一个格子和上下左右连通）
  • 八连通，在八连通的条件下，两个格子相邻当且仅当它们有相邻的边或相邻的点（即一个格子的上下左右已经斜边四个角）

如图，在四连通的条件下，黄色块和蓝色块相邻，但是黄色块和白色块不相邻。在八连通的条件下，黄色块和蓝色块以及白色块都相邻。

油田

题目大意:

输入一个\(n\)行\(m\)列的字符矩阵，统计字符"@"组成多少个八连块。如果两个字符"@"所在的格子相邻（横、竖或者对角线方向），就说它们属于同一个八连块。

输入

1
2
3
4
5
6
5 5
****@
*@@*@
*@**@
@@@*@
@@**@

输出

1
2

所谓连块，想象一个水塘，互相连接组成一个大的块，我们称为连块。

如果计算连块的数量呢，我们可以脑动模拟一下，如果你站在一个油田先把它占了，你的四周如果有油田的话，你可以派自己的分身把它们占了，到了新的的油田，继续搜寻周围，然后往复，知道所有我们能到达的油田都被我们占了。这样这个地方就是一个连通块，那么继续全局找其它油田。

我们很容易想到一个递归算法(伪代码)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 定义search(x,y)为搜寻位置为(x,y)的油田
// tag 表示之前是否占领过
search(x,y)
    // 一定要注意，跳出格子了，我们跳过
    if(x <1 || x>n || y<1 || y>m)
        return;
    // 如果这一片不是油田，我们直接跳过，这里以前占领国，我们也跳过
 	if M[x,y] != '@' || tag[x,y]
        return
       
    // 标记一下这里被占领了
    tag[x,y]=true;
    // 然后往四个方向尝试
	search(x+1,y);
    search(x,y+1);
    search(x-1,y);
    search(x,y-1);

那么我们如何计数呢，如果我们发现一个新的之前没有找到过，那么我们计数器就+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
#include <stdio.h>
#include <ctype.h>

const int maxn = 105;
int n, m;
char M[maxn][maxn];
int tag[maxn][maxn];

void search(int x, int y)
{
    if (x < 1 || x > n || y < 1 || y > m)
        return;
    if (M[x][y] != '@' || tag[x][y])
        return;
    tag[x][y] = 1;

    search(x + 1, y);
    search(x, y + 1);
    search(x - 1, y);
    search(x, y - 1);
}

char getch()
{
    char ch = getchar();
    while (isspace(ch))
        ch = getchar();
    return ch;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            M[i][j] = getch();
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (tag[i][j] || M[i][j] != '@')
                continue;
            ans++;
            search(i, j);
        }
    printf("%d", ans);
    return 0;
}

这里解决的是四连通的问题，题目问的是八连通，我们当然可以写很多search。但是这样很麻烦。我们介绍两种方便的方法。

  1. 写好位移坐标,dx,dy

    1
    2
    3
    4
    5
    6
    7
    int dx[] = {1, 1, 1, 0, 0, -1, -1, -1, -1};
    int dy[] = {0, -1, -1, 1, -1, 1, 0, -1};

    // 然后就可以用循环快速生成八个坐标

        for (int i = 0; i < 8; i++)
            search(x + dx[i], y + dy[i]);

  2. 直接二重循环（注意对四连通不适用，四连通用法1，或依次枚举）

    1
    2
    3
    4
    5
    6
    7
    8
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (tag[i][j] || M[i][j] != '@')
                continue;
            ans++;
            search(i, j);
        }

摆格子问题

全排列

排列(permutation)定义：对于一个\(n\)个数的数组，如果1到n的整数都能从该数组找到，我们称这个数组为一个排列。比如长度为3的排列有六个。

1
2
3
4
5
6
1 2 3
1 3 2
3 1 2
3 2 1
2 1 3
2 3 1

全排列(all permutation)定义：全排列就是把长度为\(n\)的所有可能的排列都列举出来。

长度为\(n\)的排列有:\(n!\)种，我们运用小学的数学知识可以简单算出。

下面我们来考虑一个问题，给定长度\(n\)，让你按字典序输出\(n\)的全排列，即长度为\(n\)的所有排列。

  1. 首先思考，我们人脑是怎么枚举排列的，我们一般是不是先固定第一位数比如第一个数为1，然后继续枚举下面的，下面的方法就是基于这个思想，先处理完当前可能填写的情况，然后递归处理后面的数。

  2. 我们下面把要生成的\(n\)个数看成\(n\)个格子，我们目标就是把\(n\)个数填到这\(n\)个格子里。

  3. 我们开始编写递归的代码，首先递归的参数设为当前要处理的格子的位置cur，然后递归的终止条件是当前位置超出了n，这时表明我们一个排列已经生成，可以直接打印出这个排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int maxn = 15;
int P[maxn];
int n;

void dfs(int cur)
{
    // 枚举完了，注意不能写成>=n，因为第n个格子也要放数
    if (cur > n)
    {
        for (int i = 1; i <= n; i++)
        {
            printf("%d ", P[i]);
        }
        printf("\n");
        // 千万不要忘记写return
        return;
    }
}
  1. 特判下面我们要写上普通的情况，如果给你第cur个格子，你能填哪些数呢，我们可以1到n都填一下试试，然后递归到下一个格子。
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
void dfs(int cur)
{
    // 枚举完了，注意不能写成>=n，因为第n个格子也要放数
    if (cur > n)
    {
        for (int i = 1; i <= n; i++)
        {
            printf("%d ", P[i]);
        }
        printf("\n");
        // 千万不要忘记写return
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        // 第cur个格子我们放上i
        P[cur] = i;
        // 好了，当前的格子处理完了，我们通过递归转移到下一个格子
        dfs(cur + 1);
    }
}

int main()
{
    // 我们尝试枚举长度为4的全排列
    n = 4;
    // 我们要从第一个格子开始处理
    dfs(1);
    return 0;
}

  1. 运行一下我们发现它枚举的不是全排列，而是所有1到n的数组组合，为什么我们看我们把\(i\)放到第cur个格子的时候没有检查\(i\)是否在之前的格子里出现过，一个全排列一个数字只能出现一次。那么我们可以简单修改一下

    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
    void dfs(int cur)
    {
        // 枚举完了，注意不能写成>=n，因为第n个格子也要放数
        if (cur > n)
        {
            for (int i = 1; i <= n; i++)
            {
                printf("%d ", P[i]);
            }
            printf("\n");
            // 千万不要忘记写return
            return;
        }
        for (int i = 1; i <= n; i++)
        {
            // 我们来看看前面的格子有没有出现过i，出现了cur个格子不能放i了，我们就跳过.
            bool ok = true;
            for (int k = 1; k < cur; k++)
            {
                if (P[k] == i)
                {
                    ok = false;
                    break;
                }
            }
            if (!ok)
                continue;
            // 第cur个格子我们放上i
            P[cur] = i;
            // 好了，当前的格子处理完了，我们通过递归转移到下一个格子
            dfs(cur + 1);
        }
    }

上面的代码已经足够通过班级里的题目了，但是上面的代码不够快，我们观察一下检测前面格子是否出现\(i\)这一步用了一个循环，我们其实可以用vis技术，来常数时间判断，代码如下。

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
void dfs(int cur)
{
    // 枚举完了，注意不能写成>=n，因为第n个格子也要放数
    if (cur > n)
    {
        for (int i = 1; i <= n; i++)
        {
            printf("%d ", P[i]);
        }
        printf("\n");
        // 千万不要忘记写return
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[i])
            continue;

        P[cur] = i;
        // 说明P里面有i了
        vis[i] = 1;
        dfs(cur + 1);
        // 注意dfs完后我们要把i归还，因为我们会在这个格子上填其它数
        vis[i] = 0;
    }
}

八皇后问题

下面我们来看一个非常经典的问题，八皇后难题

一个如下的 \(6×6\) 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。 avatar 上面的布局可以用序列 2 4 6 1 3 5 来描述，第 ii 个数字表示在第 ii 行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。 并把它们以上面的序列方法输出，解按字典顺序排列。 请输出前 3 个解。最后一行是解的总个数。

这好像是一个升级版的全排列，其实我们要做的还是摆格子，第\(i\)个格子表示第\(i\)行皇后需要摆放的位置，格子里填的数表示皇后的列坐标。因为八皇后问题不会出现一列放两个皇后的情况，即不会出现两个格子填了相同的数，这正好是一个排列，但是还需要满足斜线不能冲突。所以这题就是全排列plus ，全排列条件+八皇后特有斜线不能冲突条件。

如果你填好了一组数，你怎么看有没有斜线冲突呢，我们初中就学过一次函数的图像，我们这里可以借助这种思想（注意对于棋盘我们一般不采用笛卡尔坐标系，而是使用行列来表示一个位置），我们发现同一个斜线它们行号减去列号好像是一个定值，反斜线行号加上列号也是一个定值。利用这个简单的数学规律我们简单修改一下全排列的代码，只多加了两个数组vis2,vis3来判定两条斜线是否被占用。

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
int P[maxn];
int vis[maxn];
int vis2[maxn];
int vis3[maxn];

void dfs(int cur)
{
    if (cur > n)
    {
        for (int i = 1; i <= n; i++)
        {
            printf("%d ", P[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] || vis2[i - cur] || vis3[i + cur])
            continue;

        P[cur] = i;
        vis[i] = 1;
        vis2[i - cur] = 1;
        vis3[i + cur] = 1;
        dfs(cur + 1);
        vis[i] = 0;
        vis2[i - cur] = 0;
        vis3[i + cur] = 0;
    }
}

等等，我们\(i-cur\)，\(i+cur\)好像会越界，\(i-cur\)会变成一个负数，那该这么办呢，\(i-cur \in \{1-n...n-1\}\)，我们可以使用加一个偏移量\(bias\)，\(i-cur+bias\)大于\(0\)。

注意题目只要输出前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
#include <iostream>
const int maxn = 15;
const int bias = 50;

int P[maxn];
int vis[maxn];

int vis2[150];
int vis3[150];

int n;
int cnt = 0;
void dfs(int cur)
{
    if (cur > n)
    {
        for (int i = 1; i <= n; i++)
        {
            printf("%d ", P[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] || vis2[i - cur + bias] || vis3[i + cur])
            continue;

        P[cur] = i;
        vis[i] = 1;
        vis2[i - cur + bias] = 1;
        vis3[i + cur] = 1;
        dfs(cur + 1);
        vis[i] = 0;
        vis2[i - cur + bias] = 0;
        vis3[i + cur] = 0;
    }
}

int main()
{
    n = 8;
    dfs(1);
    return 0;
}

货物摆放

小蓝有一个超大的仓库，可以摆放很多货物。 现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。 小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆 L、W、H 的货物，满足 \(n\) = L × W × H。给定 n，请问有多少种堆放货物的方案满足要求。

例如，当 \(n = 4\) 时，有以下 6 种方案：\(1×1×4、1×2×2、1×4×1、2×1×2、 2 × 2 × 1、4 × 1 × 1\)。 请问，当 \(n = 2021041820210418\) （注意有 16 位数字）时，总共有多少种方案？

我们首先\(\sqrt n\)求出所有因子，然后还是填方格。这里我们就是填上它的因子（可以重复），最后检查填的乘积是否等于那个数就行，但是因子可能很大，乘起来会溢出，那么我们可以在算的过程中计算出已经得到的乘积\(prod\) ，这样剩下的格子成绩要是\(V/prod\)，我们要填入格子的因子一定是\(V/prod\)的因数（想想为什么）。

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

#define i64 long long
using namespace std;

const int maxn = 1e2 + 5;
int n = 3;
i64 V = 2021041820210418;
i64 A[maxn];
i64 prod = 1;
int cnt = 0;
// 因子
vector<i64> factors;

void init()
{
    factors.push_back(1);
    factors.push_back(V);

    for (i64 i = 2; i * i <= V; i++)
    {
        if (i * i == V)
        {
            factors.push_back(i);
            break;
        }
        if (V % i == 0)
        {
            factors.push_back(i);
            factors.push_back(V / i);
        }
    }
    sort(factors.begin(), factors.end());
}
void dfs(int cur)
{
    if (cur > n)
    {
        if (prod == V)
        {
            ++cnt;
            for (int i = 1; i <= n; i++)
            {
                printf("%lld ", A[i]);
            }
            printf("\n");
        }
        return;
    }
    for (auto f : factors)
    {
        i64 r = V / prod;

        if (r % f != 0)
            continue;

        A[cur] = f;
        prod *= f;
        dfs(cur + 1);
        prod /= f;
    }
}

int main()
{
    init();
    dfs(1);
    printf("Number is %lld\n", cnt);
    return 0;
}

拓展练习：

  1. 如果不允许出现重复因子该怎么做
  2. 如果要保证后面的数大于前面的数又该怎么做。

方格填数

考虑该如何处理二维的情况

选和不选类

DFS实现子集枚举

给定一个集合，枚举所有可能的子集我们也可以通过dfs来实现。

首先我们需要知道的是如果一个集合中有\(n\)个元素，它有\(2^n\)个子集，有\(2^n-1\)个非空子集。

我们发现子集的长度都不是固定的，比如对于集合\(\{1,2,3\}\)子集的数量有\(2^3\)个非空子集有\(2^3-1\)，即\(\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\)这么多非空子集。

我们观察发现子集的最长的长度是固定的，它不会超过集合元素的个数，那么我们可以把格子放大一点能容纳下元素个数最大的集合，并且允许一些格子为空。就像这样\(\{1,-1,-1\},\{-1,2,-1\},\{-1,-1,3\},\{1,2,-1\},\{-1,2,3\},\{1,-1,3\},\{1,2,3\}\)(这里我们-1当成这个格子为空的特殊标志，当然这个数你也可以记作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
#include <iostream>
#include <vector>
using namespace std;

vector<int> Set = {1, 2, 3, 4};

// 这次我们从0号格子开始摆
int A[15];

void dfs(int cur)
{
    if (cur >= Set.size())
    {
        for (int i = 0; i < Set.size(); i++)
        {
            if (A[i] == -1)
                continue;
            printf("%d,", A[i]);
        }
        return;
    }
    A[cur] = Set[cur];
    dfs(cur + 1);
    A[cur] = -1;
    dfs(cur + 1);
}

int main()
{
    dfs(0);
    return 0;
}

我们其实可以进一步简化，使用vector的pop_back，我们根本不需要填充-1，如果选这个元素我们就push这个元素到A的末尾，如果不选我们直接往下搜即可，注意我们一定别忘记选中这种情况执行完了切换到不选的时候要pop_back，dfs(cur+1)后我们要保证变回原样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> Set = {1, 2, 3, 4};

// 这次我们从0号格子开始摆
vector<int> A;
void dfs(int cur)
{
    if (cur >= Set.size())
    {
        for (auto v : A)
            printf("%d ", v);
        printf("\n");
        return;
    }
    // 选它
    A.push_back(Set[cur]);
    dfs(cur + 1);
    // 一定别忘记选中这种情况执行完了切换到不选的时候要pop_back
    A.pop_back();

    dfs(cur + 1);
}

平衡括号计数

给定一个数\(n\)你需要找出所有满足以下条件的字符串

  • 字符串长度为\(n\)

  • 字符串只包含(和)两种字符

  • 该字符串满足括号平衡。

你只需要输出满足条件的字符串的个数，不需要输出所有字符串

例如: (),(()())括号平衡, 而)((,(()))(括号不平衡

首先我们考虑如何判断一串括号是否平衡，括号平衡需要满足两个基本条件

  • 左括号的数量和右括号的数量相同
  • 记: \(f(x)\)为第一个字符到第\(x\)个字符，左括号数量和右括号的差，比如(()( \(f(1)=1,f(2)=2,f(3)=1,f(4)=2\)，如果括号平衡一定要满足\(\forall x\in \{1...|s|\},f(x)\ge 0\)其中\(|s|\)为字符串的长度。

第一个条件十分显然，我们可以证明第二条，我们使用反证法如果\(\exists x, f(x)<0\)即表明前\(x\)字符中右括号的数量比左括号的数量多，那么一定会有一个右括号得不到配对，而\(x\)后面的左括号不能和前面的右括号配对，所以这个字符串括号一定不平衡。

检测括号平衡函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int maxn = 1005;
// 字符串从str[1]开始
char str[maxn];
int n = 4;
bool check()
{
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (str[i] == '(')
            sum++;
        else
            sum--;
        if (sum < 0)
            return false;
    }
    return sum == 0;
}

那么我们这么才能枚举所有可能的字符串呢，发现它的长度是固定的，而且每个位置只能出现(和)，我们直接把两种决策放到str即可，最后生成了一个字符串后检测是否符合条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int cur)
{
    if (cur > n)
    {
        if (check())
            printf("%s\n", str + 1);
        return;
    }
    str[cur] = '(';
    dfs(cur + 1);
    str[cur] = ')';
    dfs(cur + 1);
}

选数

已知 n 个整数 \(x_1,x_2,\cdots,x_n\)，以及 11 个整数 \(k(k<n)\)。从 \(n\) 个整数中任选 \(k\) 个整数相加，可分别得到一系列的和。例如当 \(n=4\)，\(k=3\)，\(4\) 个整数分别为 \(3,7,12,19\) 时，可得全部的组合与它们的和为：

\(3+7+12=22\)

\(3+7+19=29\)

\(7+12+19=38\)

\(3+12+19=34\)

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：\(3+7+19=29\)。

使用子集枚举，最后验证是否选了\(k\)个并且该集合之和是否为素数即可。

一些经典题目

素数环

A ring is composed of n (even number) circles as shown in diagram. Put natural numbers 1, 2, . . . , n into each circle separately, and the sum of numbers in two adjacent circles should be a prime. Note: the number of first circle should always be 1.

题目大意就是让你把1...n这n个数串成一个环，使得任意两个相邻的数和为素数。(首位必须为1)

pic

这一题我们还是暴力摆格子，注意首位加末位需要是素数，我们可以摆完后特判首位是否互素即可。

容易得到解法

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
int n;
int A[15];
int vis[15];
void dfs(int cur)
{
    if (cur > n)
    {
        if (!is_prime(A[1] + A[n]))
            return;
        for (int i = 1; i <= n; i++)
            printf("%d ", A[i]);
        printf("\n");
        return;
    }
    if (cur == 1)
    {
        A[cur] = 1;
        vis[1] = 1;
        
        dfs(cur + 1);
        
        vis[1] = 0;
        return;
    }
    else
        for (int i = 1; i <= n; i++)
        {
            if (vis[i])
                continue;
            if (is_prime(i + A[cur - 1]))
            {
                A[cur] = i;
                vis[i] = 1;
                dfs(cur + 1);
                vis[i] = 0;
            }
        }
}

一笔画

一天小明在玩一个叫一笔画的游戏，遇到了一些不会的关卡。游戏内容是这样的。给你\(n\)行\(m\)（\(1\le n,m \le 20\)）列的地图，S代表起点，.代表道路，#代表障碍物不能通过。小明想知道能不能一笔通过所有道路。

这种找出每个点都经过且都经过一次的路径我们称为哈密顿路径。哈密顿路径求解是一个\(NP\)问题，即我们没有多项式时间复杂度的算法。那么我们就可以安心的使用暴力了。

我们只要在每个点枚举四个方向走就行。时间复杂度是\(4^{nm}\)，但是因为我们只要找到一组解，所以跑起来远远没到\(4^{nm}\)规定时间内可以求出。

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
int n, m;
int vis[maxn][maxn];
char M[maxn][maxn];
int sx, sy;

char dir[] = "LRUD";
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

int white_cnt = 0;
char A[150];

bool dfs(int x, int y, int depth)
{
    if (depth == white_cnt)
        return true;

    for (int i = 0; i < 4; i++)
    {
        A[depth] = dir[i];
        int nx = x + dx[i], ny = y + dy[i];

        if (vis[nx][ny] || M[nx][ny] == '#')
            continue;
        if (nx <= 0 || nx > n || ny <= 0 || ny > m)
            continue;

        vis[nx][ny] = 1;
        if (dfs(nx, ny, depth + 1))
            return true;
        vis[nx][ny] = 0;
    }
    return false;
}

宽度优先搜索

一些经典问题

之前我们讲的DFS，都是枚举完一个解后再判断，DFS重点是枚举完了再判断处理。如果要找出步数最少的解我们就需要枚举所有可能，这样时间复杂度便是指数级，更可怕的是枚举过程中步数会不固定，可能会非常长，这样我们就无法在规定的时间内解决问题。

这时我们不妨换个思路，如果有一种算法可以先枚举第一步能到达的所有状态，检查完发现都无法满足条件，我们从第一步出发枚举所有走两步可以到达的状态是否有某一个状态能满足条件，这样一直枚举下去直到发现一组解，这组解一定使用了最少的步数。这样我们便可以不用枚举所有解了，而是根据把某一步数的所有状态都穷举完，在基于这一步向下一步迈进。

我们称之为BFS，你可以认为BFS是一层一层的搜索，而不是DFS先搜到底，然后回退到上一个状态继续找其它解。

迷宫问题

给你一个迷宫，起点为S，终点为T，.表示空格，#表示障碍物无法通过，你每次可以从当前位置上下左右移动（不能出界或者撞到障碍物上）你需要找出从起点到终点的最少步数，如果不存在解，输出-1。

第一行输入\(n,(1\le n \le 100), m(1\le m \le 100)\)表示迷宫的行数和列数

1
2
3
4
5
6
5 5
.....
...S.
####.
..T#.
.....

答案是7.

我们用dfs可以快速判断是否有解，只要S和T在同一个四连块，那么S就一定可以到达T。我们也可以dfs穷举所有路径，然后找到一条长度最短的一条。时间复杂度\(O(4^{nm})\)注意我们第三个参数depth，当然我们也可以写成全局变量，这个记录了你当前搜索的深度（即步数）

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

using namespace std;
const int maxn = 100;

int ans = 0x3f3f3f3f;
int n, m;
char M[maxn][maxn];
int vis[maxn][maxn];
int sx, sy, ex, ey;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool check_pos(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= n && !vis[x][y] && M[x][y] != '#';
}
void dfs(int x, int y, int depth)
{
    if (x == ex && y == ey)
    {
        ans = min(ans, depth);
        return;
    }

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (check_pos(nx, ny))
        {
            vis[nx][ny] = 1;
            dfs(nx, ny, depth + 1);
            vis[nx][ny] = 0;
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> M[i][j];
            if (M[i][j] == 'S')
                sx = i, sy = j;
            if (M[i][j] == 'T')
                ex = i, ey = j;
        }
    vis[sx][sy] = 1;
    dfs(sx, sy, 0);
    cout << ans << "\n";
    return 0;
}

这种方法对于很小的地图\(5\times 5\)以内，还是有可能解决的对于\(10\times 10\)这种棋盘如果障碍物不多感觉就跑不出来了。其实我们这里可以简单优化一下，如果当前深度超过了已有的解，直接退出。

1
2
3
4
5
6
7
8
9
10
void dfs(int x, int y, int depth)
{
    if(depth >= ans)
        return;
    if (x == ex && y == ey)
    {
        ans = min(ans, depth);
        return;
    }
	....

这种优化称为剪枝，可以大幅度提高dfs的速度，但是这种提升还是敌不过指数大一点所带来的运行时间膨胀，我们需要另寻他法。BFS，

我们考虑怎么才能实现bfs，一层一层的搜索，也就是先搜第一步能达到那些格子，然后从这第一步出发再走一步即第二部能到达那些格子，直到我们跑遍了所有我们能走到的格子。

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
// A[i] 表示第i步能到达哪些格子.
vector<pair<int, int>> A[10005];

void bfs()
{
    A[0].push_back({sx, sy});
    // 最多不会超过n*m-1步
    for (int i = 0; i < m * n; i++)
    {
        //我们每次都用当前步更新下一步。
        // C++ 17语法，结构化绑定，可以使用方括号依次对于迭代的每个元素成员，等价于
        /*
        for(size_t i=0;i<A[i].size();i++)
        {
            int x=A[i].first;
            int y=A[i].second;

        */
        for (auto [x, y] : A[i])
        {
            // 从x,y出发在走一步，就是走了i+1步能到哪些地方
            for (int j = 0; j < 4; j++)
            {
                int nx = x + dx[j], ny = y + dy[j];
                if (!check_pos(nx, ny))
                    continue;
                A[i + 1].push_back({nx, ny});
                // 当前访问到了nx,ny，这已经是最优了，因为后面访问到了nx,ny一定不小于i+1步。
                printf("vis[%d][%d]=%d\n", nx, ny, i + 1);
                vis[nx][ny] = i + 1;
            }
        }
    }
}

我们把每一步能到达的点都存到了A中，基于第i步一定从i-1步转移过来的，我们一定不会漏解，但是vis的存在我们可以省去很多不必要的状态，比如我们本来\(a\)步和\(b\)步都能到达一个点，但是vis的存在会忽略到步数长的状态。时间复杂度\(O(mn)\)因为每个格子只访问一遍。

这个A数组看上去很蠢，其实我们可以使用队列来模拟bfs过程。

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

using namespace std;
const int maxn = 100;

int ans = 0x3f3f3f3f;
int n, m;
char M[maxn][maxn];
int vis[maxn][maxn];
int sx, sy, ex, ey;

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

bool check_pos(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= n && vis[x][y]==-1 && M[x][y] != '#';
}
void bfs()
{
    queue<pair<int, int>> q;
    q.push({sx, sy});
    vis[sx][sy] = 0;
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();

        for (int j = 0; j < 4; j++)
        {
            int nx = x + dx[j], ny = y + dy[j];
            if (!check_pos(nx, ny))
                continue;
            q.push({nx, ny});
            vis[nx][ny] = vis[x][y] + 1;
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> M[i][j];
            if (M[i][j] == 'S')
                sx = i, sy = j;
            if (M[i][j] == 'T')
                ex = i, ey = j;
        }
    memset(vis, -1, sizeof(vis));
    bfs();
    cout << vis[ex][ey] << "\n";
    return 0;
}

马的遍历

有一个 \(n \times m\) 的棋盘，在某个点 (x, y)(x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入只有一行四个整数，分别为 n, m, x, y。

下面的题目就都是套这个bfs的模板了，首先我们先要想状态，棋盘类问题状态一般都是格子，然后我们看状态之间一步进行的转移。

由于马是走日字形的，首先将马的行走方式存储在数组中，通过dis数组记录所有的距离，直接BFS即可

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
#include <iostream>
#include <stdio.h>
#include <queue>
#include <cstring>
using namespace std;
struct Point{
    int x, y, step;
    Point(int _x, int _y, int _step):x(_x), y(_y), step(_step){}
    Point(){}
};
//用于遍历的队列
queue<Point> q;
//马一步能走的所有位置
int movex[8] = {2,-2,2,-2,-1,1,-1,1};
int movey[8] = {1,1,-1,-1,2,2,-2,-2};
//记录马走到每个点的步数
int dis[405][405];
int st_x, st_y, n, m;

void BFS(){
    //将dis初值赋值为-1同时可以起到vis的作用（避免重复搜素）
    memset(dis, 0xff, sizeof(dis));
    q.push(Point(st_x, st_y, 0));
    dis[st_x][st_y] = 0;
    while (!q.empty()){
        Point cur = q.front();
        q.pop();
        for (int i = 0; i < 8; i++){
            //下一步的x坐标
            int nxtX = cur.x + movex[i];
            //下一步的y坐标
            int nxtY = cur.y + movey[i];
            //下一步一共走的步数
            int nxtStep = cur.step + 1;
            //检测坐标是否合法
            if (nxtX >= 1 && nxtX <= m && nxtY >= 1 && nxtY <= n){
                //dis为-1说明还没有搜索过
                if (dis[nxtX][nxtY] == -1){
                    q.push(Point(nxtX, nxtY, nxtStep));
                    dis[nxtX][nxtY] = nxtStep;
                }
            }
        }
    }
}

int main(){
    cin >> n >> m >> st_y >> st_x;
    BFS();
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            printf("%-5d", dis[j][i]);
        }
        printf("\n");
    }
}

奇怪的电梯

有一台电梯，他每层楼都只能向上或向下固定的层数\(K_i\)，比如\(K_1=3\)表示该电梯在一楼时只能向上3层或者向下3层（超过总楼层或者低于1楼的都属于无法到达）问从楼层A到楼层B需要的步数（若不存在则为-1）

由于每层楼都只有固定的两个操作向上或者向下，因此我们可以从开始楼层A开始上下同时搜索，将合法的移动都添加到队列中，同时记录已经到达过的楼层，在搜索的同时检查一下是否到达楼层B即可，若为搜索到则返回-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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include <tuple>

using namespace std;
const int maxn = 1e3 + 5;
int N, A, B;
int vis[maxn];
int K[maxn];

int bfs()
{
    queue<pair<int, int>> q;
    q.push({A, 0});
    vis[A] = 0;

    while (!q.empty())
    {
        auto [p, t] = q.front();
        q.pop();
        if (p == B)
        {
            return t;
        }
        // 往上
        int np1 = p + K[p];
        // 往下
        int np2 = p - K[p];

        if (1 <= np1 && np1 <= N)
        {
            if (vis[np1] == -1)
            {
                vis[np1] = t + 1;
                q.push({np1, t + 1});
            }
        }

        if (1 <= np2 && np2 <= N)
        {
            if (vis[np2] == -1)
            {
                vis[np2] = t + 1;
                q.push({np2, t + 1});
            }
        }
    }
    return -1;
}

int main()
{
    cin >> N >> A >> B;
    memset(vis, -1, sizeof(vis));
    for (int i = 1; i <= N; i++)
        cin >> K[i];
    cout << bfs();
    return 0;
}

Meteor Shower

陨石从不同时刻T（T <= 1000）落下，每颗陨石会摧毁落点以及周围相邻的四个方格贝西从原点（0，0）出发，每走一步会花费一个时间单位，问贝西至少要走几步才能走到安全的地点（不会被陨石摧毁的方格）

由于每颗陨石在不同的时刻落下，因此我们可以在地图上记录每个方块被最早被摧毁的时间（取最小值）若不会被摧毁则为1，在bfs的时候记录当前走的步数，若下一步的时间小于被摧毁的时间则可以移动，同时判断是否为安全的方块如果是，则可以直接返回步数。

我们这里用两个vis来记录，vis代表这个格子被摧毁的时间，而vis2代表Bassie之前bfs过程中是否走过这个格子，走过就不要再走了（好牛不走回头路，因为在回头走的话时间复杂度就变成指数级）

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

using namespace std;
const int maxn = 1e3 + 5;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};

int n;
int vis[maxn][maxn];
int vis2[maxn][maxn];

bool check_pos(int x, int y)
{
    if (x < 0 || x > 500 || y < 0 || y > 500)
        return false;
    return true;
}

int bfs()
{
    queue<tuple<int, int, int>> q;
    q.push({0, 0, 0});
    vis2[0][0] = 1;
    while (!q.empty())
    {
        auto [x, y, t] = q.front();
        q.pop();

        if (vis[x][y] > 1e9)
            return t;

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (!check_pos(nx, ny) || vis2[nx][ny])
                continue;

            if (vis[nx][ny] > t + 1)
            {
                q.push({nx, ny, t + 1});
                vis2[nx][ny] = 1;
            }
        }
    }
    return -1;
}

int main()
{
    cin >> n;

    memset(vis, 0x3f, sizeof(vis));

    for (int i = 1; i <= n; i++)
    {
        int x, y, t;
        cin >> x >> y >> t;
        vis[x][y] = min(vis[x][y], t);
        for (int j = 0; j < 4; j++)
        {
            int nx = x + dx[j], ny = y + dy[j];
            if (check_pos(nx, ny))
            {
                vis[nx][ny] = min(vis[nx][ny], t);
            }
        }
    }
    cout << bfs();
    return 0;
}

复杂状态的bfs

八数码难题

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

如何判断状态，3x3白块的位置？我们发现这个状态所含的信息是不完整的，因为你白块移动了还会影响到其它数字，告诉你一个小技巧，我们可以看我们需要到达哪里，题目中我们需要到达目标状态 123804765，这是一个字符串，我所以我们状态就定为这样的字符串，通过这个9个数字我们可以重建3x3的棋盘。然后移动白块形成新的状态作为下一步，这样我们朴素的bfs即可解决这个问题。

我们的代码直接按字符顺序充填棋盘，我们其实可以把这个字符串看作一个全排列（0看作1，1看作2以此类推），然后使用康托展开（相当于对一个排列哈希）来获取状态的整数编码，有关康托展开的内容这里就不在赘述。有兴趣的同学可以自行了解。

本题有许许多多的优化方法，常用的两种分别是双向搜索和启发式搜索，对于更大的棋盘比如12数码问题，我们的朴素bfs会超时，有关双向搜索和启发式搜索可以自行上网了解。

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
#include <iostream>
#include <set>
#include <queue>
#include <string>

using namespace std;
int M[3][3];
set<string> vis;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
// 将字符串转换为地图
pair<int, int> convert(const std::string &str)
{
    pair<int, int> ret;
    for (int i = 0; i < str.size(); i++)
    {
        M[i / 3][i % 3] = str[i] - '0';
        if (str[i] == '0')
            ret = {i / 3, i % 3};
    }
    return ret;
}

string inv_convert()
{
    string ret;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            ret.push_back(M[i][j] + '0');
    return ret;
}
bool check_pos(int x, int y)
{
    return x >= 0 && x < 3 && y >= 0 && y < 3;
}
int bfs(const string &start, const string &dest)
{
    if (start == dest)
        return 0;

    queue<pair<string, int>> q;
    q.push({start, 0});
    vis.insert(start);

    while (!q.empty())
    {
        auto [cur, cnt] = q.front();
        q.pop();
        auto [x, y] = convert(cur);

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (!check_pos(nx, ny))
                continue;

            swap(M[nx][ny], M[x][y]);
            string nxt = inv_convert();

            if (nxt == dest)
                return cnt + 1;

            if (!vis.count(nxt))
            {
                vis.insert(nxt);
                q.push({nxt, cnt + 1});
            }
            // 一定别忘记换回来
            swap(M[nx][ny], M[x][y]);
        }
    }
    return -1;
}
int main()
{
    string start;
    cin >> start;
    cout << bfs(start, "123804765");
    return 0;
}

课后练习: 扭密码箱

你新买了一个密码箱，密码箱支持4位数密码，每一位都是数字0到9，这个密码箱是旋转式的，所以0下面一个是9，上面一个是1。刚买到箱子锁上显示0000，你知道它的密码，现在问你最少多少步可以将它解开。

每一步你都可以将相邻的几个数位往同一方向扭动一个格子，比如0000一步可以到达1111或者0111，0110，1100，0100，9999，0999等等，但是不能一步扭到0101或者0190,0200等不合法的状态.

这题稍微麻烦了一点，但是还是很好想暴力BFS即可，把这个四位数看成一个状态，然后梳理好怎么转移跑bfs即可。

其实这是ICPC2021沈阳真题，是一道铜牌题。原题是一个状态扭到另一个状态，而且给了非常多组数据，其实我们只要写完这题，然后所有两个状态的距离可以转换为0扭到它们的之间的位差状态，简单来说\(a\)扭到\(b\)可以转化为\(0\)扭到\(c\)，而\(c=b-a\)(（不进位减法)。这样预处理可能花点时间，后面只要\(O(1)\)查表就得到了答案。

  1. 大于最大时间1000即可，为方便起见本题可设为0x3f3f3f3f↩︎