进阶搜索思路#

启发式搜索#

启发式搜索（英文：heuristic search）是一种在普通搜索算法的基础上引入了启发式函数的搜索算法．
启发式函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支．简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解

通过一个估价函数，我们可以有效减少搜索时枚举的状态，进行有效剪枝。

设当前点为 u，已经走了 f(u) 步，估价函数为 h(u)，u 到终点的实际距离为 g(u)，则根据启发式搜索的思想，需要满足 $h(u)\leqslant g(u)$ ，所以我们要以 $f(u)+h(u)$ 为关键字进行排序（类似于）

BFS#

BFS 可以解决的问题可大致分为两类：最短距离（类似走迷宫）和最小步数（类似八数码）

BFS 具有两个性质：路径最短（第一次走到的点一定最短）和“基于迭代”（不会爆栈）

四联通一般用 dx[]，即偏移量数组

八连通一般用两重循环，枚举一个 3*3 的矩阵（注意忽略中心点）

BFS#

Flood Fill#

将一张图上的点抽象为“洼地”和“凸起”，每一次任选一个“洼地”点，想象有一个无限多的水源向里注水，直到所有的“洼地”都被灌满水源，该算法被命名为 Flood Fill
Flood Fill 可以在线性的时间复杂度内，找到某个点所在的连通块
扩展格子的过程，可以使用 DFS 或 BFS，但 DFS 可能爆栈，且在数据规模大的时候复杂度很高，所以尽可能使用 BFS 实现。

池塘计数（Flood Fill 裸题）#

注意：本题为八联通的情况。

从前往后扫描，如果某个点是水而且没有被覆盖过，就从该点开始执行 Flood Fill

在 BFS 过程中，如果发生越界/该点不是水/该点被遍历过，就 continue 这个坐标

Code#

1
// Problem: 池塘计数
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1099/
4
// Time: 2026-03-22 22:34:17
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 1010;
8
typedef pair<int, int> PII;
9

10
int n, m;
11
char g[N][N];
12
bool vis[N][N]; // 加入判重，保证每个点只会入队一次，保证线性的复杂度
13
int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
14
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
15

16
void bfs(int stx, int sty)
17
{
18
    queue<PII> q;
19
    q.push({stx, sty});
20
    vis[stx][sty] = true;
21

22
    while (q.size())
23
    {
24
        auto t = q.front();
25
        q.pop();
26

27
        int a = t.first, b = t.second;
28

29
        for (int i = 0; i < 8; i++)
30
        {
31
            int x = a + dx[i], y = b + dy[i];
32

33
            if (x < 0 || x >= n || y < 0 || y >= m) // 出界
34
                continue;
35
            if (g[x][y] == '.' || vis[x][y]) // 不是水或者已被遍历过
36
                continue;
37

38
            q.push({x, y});
39
            vis[x][y] = true;
40
        }
41
    }
42
}
43

44
int main()
45
{
46
    cin >> n >> m;
47
    for (int i = 0; i < n; i++)
48
        for (int j = 0; j < m; j++)
49
            cin >> g[i][j];
50

51
    int cnt = 0;
52
    for (int i = 0; i < n; i++)
53
        for (int j = 0; j < m; j++)
54
            if (g[i][j] == 'W' && !vis[i][j])
55
            {
56
                bfs(i, j);
57
                cnt++;
58
            }
59

60
    cout << cnt << endl;
61
    return 0;
62
}

城堡问题（二进制枚举 + 统计联通块面积）#

注意：本题为四联通的情况。

本题输入比较特别，对于每个格子表示的“墙”的情况，可以使用二进制编码的方式处理

也就是说，整个城堡的地形图是以数字的形式给出的。

在 bfs 过程中，如果遇到出界/该点被搜过/某个方向上有墙，则 continue 这个点/这个方向

可以在出队或入队时统计 area

Code#

1
// Problem: 城堡问题
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1100/
4
// Time: 2026-03-22 23:22:13
5
#include <bits/stdc++.h>
6
using namespace std;
7
typedef pair<int, int> PII;
8
const int N = 55;
9

10
int n, m;
11
int g[N][N];
12
bool st[N][N];
13

14
int dx[4] = {0, -1, 0, 1};
15
int dy[4] = {-1, 0, 1, 0};
16

17
int bfs(int stx, int sty)
18
{
19
    int area = 0;
20
    queue<PII> q;
21
    q.push({stx, sty});
22
    st[stx][sty] = true;
23

24
    while (q.size())
25
    {
26
        auto t = q.front();
27
        q.pop();
28

29
        area++;
30

31
        int a = t.first, b = t.second;
32

33
        // 此处同时枚举了四个运动方向和二进制数的每一位
34
        for (int i = 0; i < 4; i++)
35
        {
36
            int x = a + dx[i], y = b + dy[i];
37
            if (st[x][y] || x < 0 || x >= n || y < 0 || y >= m)
38
                continue;
39

40
            if (g[a][b] >> i & 1) // 二进制上第i位为1，即有墙
41
                continue;
42

43
            q.push({x, y});
44
            st[x][y] = true;
45
        }
46
    }
47
    return area;
48
}
49

50
int main()
51
{
52
    cin >> n >> m;
53
    for (int i = 0; i < n; i++)
54
        for (int j = 0; j < m; j++)
55
            cin >> g[i][j];
56

57
    int cnt = 0, mx_area = 0;
58
    for (int i = 0; i < n; i++)
59
        for (int j = 0; j < m; j++)
60
            if (!st[i][j])
61
            {
62
                int ret = bfs(i, j);
63
                mx_area = max(mx_area, ret);
64
                cnt++;
65
            }
66
    cout << cnt << '\n' << mx_area << endl;
67
    return 0;
68
}

山峰和山谷（判断联通块类型）#

注意：本题为八联通的情况。是否 continue 中心的那个格子对答案没有影响

首先用 Flood Fill 把整张图的联通块统计出来，在统计联通块的同时，统计每一个点周围有没有比他高/比他矮的点，根据这两个条件判断是山峰还是山谷。

如果一个联通块周围既有比他高的，也有比他矮的，这个联通块就什么都不是。

Code#

1
// Problem: 山峰和山谷
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1108/
4
// Time: 2026-03-23 13:46:03
5
#include <bits/stdc++.h>
6
using namespace std;
7
typedef pair<int, int> PII;
8
const int N = 1010;
9

10
int n;
11
int g[N][N];
12
bool st[N][N];
13

14
void bfs(int stx, int sty, bool &high, bool &low)
15
{
16
    queue<PII> q;
17
    q.push({stx, sty});
18
    st[stx][sty] = true;
19

20
    while (q.size())
21
    {
22
        auto t = q.front();
23
        q.pop();
24

25
        int a = t.first, b = t.second;
26

27
        // 注：(x, y) == (a, b)的情况不管考虑还是不考虑都是对的
28
        for (int x = a - 1; x <= a + 1; x++)
29
            for (int y = b - 1; y <= b + 1; y++)
30
            {
31
                if (x == a && y == b)
32
                    continue;
33
                if (x < 0 || x >= n || y < 0 || y >= n)
34
                    continue;
35

36
                if (g[x][y] != g[a][b]) // 此时(a, b)是山脉的边界
37
                {
38
                    if (g[x][y] > g[a][b])
39
                        high = true;
40
                    else
41
                        low = true;
42
                }
43
                else if (!st[x][y]) // 不是边界且还没被搜过的时候，才要继续搜
44
                {
45
                    q.push({x, y});
46
                    st[x][y] = true;
47
                }
48
            }
49
    }
50
}
51

52
int main()
53
{
54
    cin >> n;
55
    for (int i = 0; i < n; i++)
56
        for (int j = 0; j < n; j++)
57
            cin >> g[i][j];
58

59
    int peak = 0, valley = 0;
60

61
    for (int i = 0; i < n; i++)
62
        for (int j = 0; j < n; j++)
63
        {
64
            if (!st[i][j])
65
            {
66
                bool high = false, low = false;
67
                bfs(i, j, high, low);
68

69
                if (!high) // 联通块周围没有更高的
70
                    peak++;
71
                if (!low) // 联通块周围没有更矮的
72
                    valley++;
73
            }
74
        }
75
    cout << peak << " " << valley << endl;
76
    return 0;
77
}

最短路模型#

在整张图的边权均为 1 的时候，可以使用 BFS 按层遍历的特性来求最短路
BFS 中的队列相当于 Dijkstra 的优先队列，且保证队头的距离最小的性质

走迷宫（BFS 过程中记录路径）#

在最简单的 bfs 走迷宫问题的基础上，要求输出任意一条最短路径。

开一个 pre 数组记录所有点的前驱，初始化为 {-1, -1} 表示未访问，并把起点的前驱标作 {0, 0}

最后从终点倒着搜到起点，别忘了 push 进起点的坐标

Code#

1
// Problem: 迷宫问题
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1078/
4
// Time: 2026-03-23 15:18:49
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 1010;
8
typedef pair<int, int> PII;
9

10
int n;
11
int g[N][N];
12
int dx[4] = {0, 0, -1, 1};
13
int dy[4] = {-1, 1, 0, 0};
14
PII pre[N][N];
15
vector<PII> res;
16

17
void bfs(int stx, int sty)
18
{
19
    queue<PII> q;
20
    q.push({stx, sty});
21
    pre[stx][sty] = {0, 0};
22

23
    while (q.size())
24
    {
25
        auto t = q.front();
26
        q.pop();
27

28
        int a = t.first, b = t.second;
29

30
        for (int i = 0; i < 4; i++)
31
        {
32
            int x = a + dx[i], y = b + dy[i];
33
            if (x >= 0 && x < n && y >= 0 && y < n && g[x][y] == 0 && pre[x][y].first == -1)
34
            {
35
                q.push({x, y});
36
                pre[x][y] = {a, b};
37
            }
38
        }
39
    }
40
}
41

42
int main()
43
{
44
    cin >> n;
45
    for (int i = 0; i < n; i++)
46
        for (int j = 0; j < n; j++)
47
            cin >> g[i][j];
48

49
    for (int i = 0; i < n; i++)
50
        for (int j = 0; j < n; j++)
51
            pre[i][j] = {-1, -1};
52

53
    bfs(0, 0);
54

55
    PII pos = {n - 1, n - 1};
56
    while (pos != make_pair(0, 0))
57
    {
58
        res.push_back(pos);
59
        pos = pre[pos.first][pos.second];
60
    }
61
    res.push_back({0, 0});
62

63
    reverse(res.begin(), res.end());
64

65
    for (auto t: res)
66
        cout << t.first << " " << t.second << endl;
67
    return 0;
68
}

武士风度的牛（按日字形 BFS）#

注意：相比于传统的四联通和八连通，本题的八连通比较特殊，按照“日”字的规则来写偏移量即可

由于每个边的权重都一样，所以可以使用 BFS 来求最短路，和走迷宫的原理完全相同

Code#

1
// Problem: 武士风度的牛
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/190/
4
// Time: 2026-03-23 22:43:35
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 155;
8
typedef pair<int, int> PII;
9

10
int n, m, dist[N][N];
11
char g[N][N];
12

13
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
14
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
15

16
int bfs(int stx, int sty)
17
{
18
    memset(dist, -1, sizeof dist);
19

20
    queue<PII> q;
21
    q.push({stx, sty});
22
    dist[0][0] = 0;
23

24
    while (q.size())
25
    {
26
        auto t = q.front();
27
        q.pop();
28

29
        int a = t.first, b = t.second;
30
        for (int i = 0; i < 8; i++)
31
        {
32
            int x = a + dx[i], y = b + dy[i];
33

34
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '*' && dist[x][y] == -1)
35
            {
36
                q.push({x, y});
37
                dist[x][y] = dist[a][b] + 1;
38

39
                // 此时第一次搜到H，但还没有走到H，还需要走一步，所以return +1
40
                if (g[x][y] == 'H')
41
                    return dist[x][y] + 1;
42
            }
43
        }
44
    }
45
    return -1;
46
}
47

48
int main()
49
{
50
    cin >> m >> n;
51

52
    int stx, sty;
53

54
    for (int i = 0; i < n; i++)
55
        for (int j = 0; j < m; j++)
56
        {
57
            cin >> g[i][j];
58
            if (g[i][j] == 'K')
59
                stx = i, sty = j;
60
        }
61

62
    cout << bfs(stx, sty) << endl;
63
    return 0;
64
}

抓住那头牛（一维 BFS）#

根据题意，我们不应该走到数轴上小于 0 的点，因为这样会浪费步数

另外我们可以发现先乘 2 再减，不如先减再乘 2，所以空间只需要开到 1e5 级别

在符合条件的状况下，使用 BFS 暴搜每种情况即可，枚举的情况是有限的，且都在 [0,10000] 里，所以最多搜索 100000 次，不会 TLE

Code#

1
// Problem: 抓住那头牛
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1102/
4
// Time: 2026-03-23 23:41:24
5
#include <bits/stdc++.h>
6
using namespace std;
7
typedef pair<int, int> PII;
8
const int N = 100010;
9

10
int n, k;
11
int dist[N];
12

13
int bfs()
14
{
15
    memset(dist, -1, sizeof dist);
16

17
    queue<int> q;
18
    q.push(n);
19

20
    dist[n] = 0;
21

22
    while (q.size())
23
    {
24
        int t = q.front();
25
        q.pop();
26

27
        if (t == k)
28
            return dist[k];
29

30
        if (t + 1 < N && dist[t + 1] == -1)
31
        {
32
            dist[t + 1] = dist[t] + 1;
33
            q.push(t + 1);
34
        }
35

36
        if (t - 1 < N && dist[t - 1] == -1)
37
        {
38
            dist[t - 1] = dist[t] + 1;
39
            q.push(t - 1);
40
        }
41

42
        if (t * 2 < N && dist[t * 2] == -1)
43
        {
44
            dist[t * 2] = dist[t] + 1;
45
            q.push(t * 2);
46
        }
47
    }
48

49
    return -1;
50
}
51

52
int main()
53
{
54
    cin >> n >> k;
55
    cout << bfs() << endl;
56
    return 0;
57
}

多源 BFS#

在这种具有多个等价的起始状态的问题中，只需要在 BFS 之前把所有起始状态全部插入队列。根据 BFS 搜索的性质，这个过程就相当于每个起点都向外扩展 1 层，再扩展 2 层、3 层，以此类推。
这种做法被称为多源 BFS，即多起点的 BFS

矩阵距离#

思路#

本题可看作一个有多个起始状态的 Flood Fill，把矩阵中的每一个 1 都看作起点，整个矩阵的所有位置都可以通行，对于每个位置，在从任何一个起点出发都可以的情况下，求到达该位置所需要的最小步数。

同理，每个点第一次被访问的时候，就相当于距离他最近的那个起点扩展到了它。

Code#

1
// Problem: 矩阵距离
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/175/
4
// Time: 2026-03-24 13:04:12
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 1010;
8

9
int n, m;
10
char g[N][N];
11
int dist[N][N];
12
int dx[4] = {0, 0, 1, -1};
13
int dy[4] = {1, -1, 0, 0};
14

15
void bfs()
16
{
17
    memset(dist, -1, sizeof dist);
18

19
    queue<pair<int, int>> q;
20
    for (int i = 0; i < n; i++)
21
        for (int j = 0; j < m; j++)
22
        {
23
            if (g[i][j] == '1')
24
            {
25
                q.push({i, j});
26
                dist[i][j] = 0;
27
            }
28
        }
29

30
    while (q.size())
31
    {
32
        auto t = q.front();
33
        q.pop();
34

35
        int a = t.first, b = t.second;
36
        for (int i = 0; i < 4; i++)
37
        {
38
            int x = a + dx[i], y = b + dy[i];
39
            if (x >= 0 && x < n && y >= 0 && y < m && dist[x][y] == -1)
40
            {
41
                q.push({x, y});
42
                dist[x][y] = dist[a][b] + 1;
43
            }
44
        }
45
    }
46
}
47

48
int main()
49
{
50
    cin >> n >> m;
51

52
    for (int i = 0; i < n; i++)
53
        for (int j = 0; j < m; j++)
54
            cin >> g[i][j];
55

56
    bfs();
57

58
    for (int i = 0; i < n; i++)
59
    {
60
        for (int j = 0; j < m; j++)
61
        {
62
            cout << dist[i][j] << " ";
63
        }
64
        cout << '\n';
65
    }
66

67
    return 0;
68
}

最小步数模型#

最小步数模型往往关注整张图，把它作为 bfs 的对象，所有状态可以构成一张有向图。一般通过哈希的方式，将每种状态存下来，然后进行 BFS，直到发现终点状态为止
例如在八数码中，就是通过交换，从起点图走到终点图

八数码-基础 BFS 解法#

魔板#

思路#

本题需要记录方案，类似于

由于要求按字典序输出，所以调整搜索方式即可。

题目给定如下三种操作，不一定需要把它转成二维，找规律在一维上直接操作即可：

交换上下两行【把一维表示整个倒过来】
将最右边的一列插入到最左边【把字符串第 3 位（从 0 开始）挪到最前面，把第 4 位挪到最后面】
中央的四个数顺时针旋转【交换第 1 位和第 2 位，交换第 1 位和第 5 位，交换第 1 位和第 6 位（第一位实时更新）】

Code#

1
// Problem: 魔板
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1109/
4
// Time: 2026-03-24 13:39:45
5
#include <bits/stdc++.h>
6
using namespace std;
7
unordered_map<string, string> mp; // now - pre
8

9
string opA(string s)
10
{
11
    reverse(s.begin(), s.end());
12
    return s;
13
}
14

15
string opB(string s)
16
{
17
    for (int i = 3; i > 0; i--)
18
    {
19
        swap(s[i], s[i - 1]);
20
        swap(s[7 - i], s[8 - i]);
21
    }
22
    return s;
23
}
24

25
string opC(string s)
26
{
27
    swap(s[1], s[2]);
28
    swap(s[1], s[5]);
29
    swap(s[1], s[6]);
30
    return s;
31
}
32

33
void bfs(string begin, string end)
34
{
35
    queue<string> q;
36
    q.push(begin);
37
    mp[begin] = "";
38

39
    while (q.size())
40
    {
41
        string t = q.front();
42
        q.pop();
43

44
        string res[3] = {opA(t), opB(t), opC(t)};
45

46
        for (int i = 0; i < 3; i++)
47
        {
48
            string s = res[i];
49
            if (!mp.count(s))
50
            {
51
                mp[s] = mp[t] + char('A' + i);
52
                if (mp[s] == end)
53
                    return;
54
                q.push(s);
55
            }
56
        }
57
    }
58
}
59

60
int main()
61
{
62
    string begin = "12345678", end;
63
    for (int i = 0; i < 8; i++)
64
    {
65
        int x;
66
        cin >> x;
67
        end = end + char(x + '0');
68
    }
69

70
    if (begin != end)
71
        bfs(begin, end);
72

73
    cout << mp[end].size() << '\n' << mp[end];
74
    return 0;
75
}

双端队列 BFS#

双端队列 BFS 通常用于解决图中边的权值只有 0 或者 1 的最短路问题
具体地说，如果入队的格点具有两段性，就要用双端队列维护。
一般情况下，我们把没有权值的边扩展到的点放到队首，有权值的边扩展到的点放到队尾．这样即可保证像普通 BFS 一样整个队列队首到队尾权值单调不下降。
具体来讲，每次都需要队头取出点，但在入队时更优的从队头入队，不优的从队尾入队，这就保证了更优的先出队，先扩展。

注意：更新其他点的时候，并不是最短距离，这个点出队的时候才是最短距离。也就是和一样，必须在出队时才知道每个点最终的最小值。

电路维修#

思路#

首先把电路板上每一个格子点(交叉点)看作无向图中的节点，我们认为两个节点 x 和 y 是某个小方格的两个对角，那么如果说 x 和 y 的线段是\，那么我们可以认为边权为 0，反之如果 x 和 y 线段是’/’，那么我们的边权视为 1，说明要旋转一次才能够连上。

每个格点周围有 4 个对角格点，出界的不走，不能更优的不走。可走的分两类：连通的和不连通的，且连通的一定比不连通的更优（因为不消耗代价）。因此，入队的格点具有两段性（0 或 1），这就需要用双端队列维护。更优的从队头入队，不优的从队尾入队，这就保证了更优的先出队，先扩展。

注意：每个状态可能入队多次，但只会扩展一次。第一次出队时即该状态的最小代价。

board1

Code#

1
// Problem: 电路维修
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/177/
4
// Time: 2026-03-24 16:20:07
5
#include <bits/stdc++.h>
6
using namespace std;
7
typedef pair<int, int> PII;
8
const int N = 510;
9

10
int n, m;
11
char g[N][N]; // 存储格内斜边
12
int dist[N][N]; // 存储操作步数
13
bool st[N][N]; // 判重
14

15
int dx[4] = {-1, -1, 1, 1};
16
int dy[4] = {-1, 1, 1, -1};
17

18
int ix[4] = {-1, -1, 0, 0};
19
int iy[4] = {-1, 0, 0, -1};
20

21
char cs[5] = "\\/\\/"; // 格内斜边的状态
22

23
int bfs()
24
{
25
    deque<PII> q;
26
    q.push_back({0, 0});
27

28
    memset(st, 0, sizeof st);
29
    memset(dist, 0x3f, sizeof dist);
30

31
    dist[0][0] = 0;
32

33
    while (q.size())
34
    {
35
        auto t = q.front();
36
        q.pop_front();
37

38
        int a = t.first, b = t.second;
39

40
        if (a == n && b == m)
41
            return dist[a][b];
42

43
        if (st[a][b])
44
            continue;
45
        st[a][b] = true;
46

47

48
        for (int i = 0; i < 4; i++) // 枚举四个方向
49
        {
50
            int x = a + dx[i], y = b + dy[i]; // 枚举格点周围的四个格点
51
            int ga = a + ix[i], gb = b + iy[i]; // 枚举格子坐标
52

53
            int w = g[ga][gb] != cs[i]; // 当不连通的时候w为1
54
            int d = dist[a][b] + w;
55

56
            if (x < 0 || x > n || y < 0 || y > m) // 跳过格点越界
57
                continue;
58
            if (ga < 0 || ga >= n || gb < 0 || gb >= m)
59
                continue;
60

61
            if (d < dist[x][y])
62
            {
63
                dist[x][y] = d;
64
                if (w == 0)
65
                    q.push_front({x, y});
66
                else
67
                    q.push_back({x, y});
68
            }
69
        }
70
    }
71
    return 0x3f3f3f3f;
72
}
73

74
void solve()
75
{
76
    cin >> n >> m;
77

78
    for (int i = 0; i < n; i++)
79
        for (int j = 0; j < m; j++)
80
            cin >> g[i][j];
81

82
    int res = bfs();
83
    if (res == 0x3f3f3f3f)
84
        puts("NO SOLUTION");
85
    else
86
        cout << res << endl;
87
    return;
88
}
89

90
int main()
91
{
92
    int T;
93
    cin >> T;
94

95
    while (T--)
96
        solve();
97
    return 0;
98
}

双向 BFS#

双向 BFS 是 BFS 优化的一种策略，在给定起点和终点状态，且暴力 BFS 的状态情况很多时可以使用。
核心搜索与剪枝策略：搜索过程中，以起点和终点为搜索树的树根进行搜索，每次选择当前搜索分支较少的一段进行扩展，这样可以有效避免搜索很多无用状态。

字串变换#

思路#

题目要求最小的变换步数，可以想到 BFS，而给定起点和终点，可以想到使用双向 BFS

具体做法如下：

建立两个队列 qa，qb，分别从起点和终点开始搜索（起点和终点作为两棵搜索树的两个根），两边轮流向外进行扩展，每次扩展一整层（扩展单点容易 TLE，也有可能搜不到答案）

每次扩展后，比较两棵 BFS 树，优先扩展当前层状态数量较少的那一棵，以便于控制每棵树长得不会太胖（让搜索情况少一些）
还需要开两个哈希表 mpa，mpb，存储从树根到当前串的操作步数。同时哈希表还可以判重，避免相同的状态重复入队。
在 BFS 搜索过程中，如果发现新串同时出现在另一个哈希表里，说明两棵树回合了，此时返回操作步数。根据题目要求，如果搜完 10 步（即向下扩展 10 层）以后还没有汇合，则无答案

Code#

1
// Problem: 字串变换
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/192/
4
// Time: 2026-03-25 21:14:18
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 7; // 至多6个规则
8

9
string A, B, a[N], b[N];
10
int n;
11

12
int extend(queue<string> &q, unordered_map<string, int> &mpa, unordered_map<string, int> &mpb, string a[], string b[])
13
{
14
    int sz = q.size();
15

16
    while (sz--) // 每次扩展一层
17
    {
18
        auto t = q.front(); // 父串出队
19
        q.pop();
20

21
        // 对取出的字符串t，枚举所有的规则和所有的位置
22
        // 如果发现可以匹配规则a[i]，就生成一个新的字符串s
23
        for (int i = 0; i < n; i++) // 枚举规则
24
        {
25
            for (int j = 0; j < t.size(); j++) // 枚举父串的每个位置
26
            {
27
                if (t.substr(j, a[i].size()) == a[i])
28
                {
29
                    string s = t.substr(0, j) + b[i] + t.substr(j + a[i].size());
30

31
                    // 如果当前方向已经搜过这个字符串了，为防止死循环，直接跳过
32
                    if (mpa.count(s))
33
                        continue;
34

35
                    if (mpb.count(s)) // 正向和逆向的搜索在此处相遇，此时的总步数即为两端相加，再加上当前这一步
36
                        return mpa[t] + mpb[s] + 1;
37

38
                    mpa[s] = mpa[t] + 1;
39
                    q.push(s);
40
                }
41
            }
42
        }
43
    }
44

45
    return 11; // extend过程中如果没相遇就返回11
46
}
47

48
int bfs()
49
{
50
    if (A == B)
51
        return 0;
52

53
    queue<string> qa, qb; // 存储每个字符串状态
54
    unordered_map<string, int> mpa, mpb;
55
    // mpa存储从起点到当前串的操作步数，mpb存储从终点到当前串的操作步数
56

57
    qa.push(A), qb.push(B);
58
    mpa[A] = mpb[B] = 0;
59

60
    int step = 10, res;
61
    while (step--)
62
    {
63
        if (qa.size() <= qb.size()) // 每次选当前搜索分支较少的一段进行扩展
64
            res = extend(qa, mpa, mpb, a, b);
65
        else
66
            res = extend(qb, mpb, mpa, b, a); // 注意从b开始搜的时候要反着传参
67

68
        if (res <= 10)
69
            return res;
70
    }
71
    return 11; // 10步以内搜不到
72
}
73

74
int main()
75
{
76
    cin >> A >> B;
77
    while (cin >> a[n] >> b[n]) // 记录规则数
78
        n++;
79

80
    int res = bfs();
81
    if (res == 11)
82
        puts("NO ANSWER!");
83
    else
84
        cout << res << endl;
85

86
    return 0;
87
}

A*#

A* 搜索算法（A* search algorithm，A* 读作 A-star），简称 A* 算法，是一种在带权有向图上，找到给定起点与终点之间的最短路径的算法．它属于图遍历（graph traversal）和最佳优先搜索算法（best-first search），亦是 BFS 的改进，适用于搜索状态比较庞大的情况，可有效进行优化。

基本搜索流程#

前置知识：

首先将 BFS 中的队列改为优先队列（小根堆），根据启发式搜索的思路，我们需要存储从起点到当前点的实际距离和从当前点走到终点的估计距离，每次扩展时我们挑一个估计距离最小的点来扩展。注意：当终点第一次出队的时候 break 掉。

性质#

DFS#

DFS 的回溯是由系统栈实现的，在代码里并不体现：

board2

连通性模型#

DFS 可以判断连通性，但不保证路径最短。但 DFS 的码速比较快，且逻辑更清晰。
注意：在内部进行 dfs 搜索不需要恢复现场。

走迷宫#

注意：在走迷宫问题中，当我们以一个点向四个方向进行内部搜索的时候，是不需要“还原现场”的，因为不管怎么搜，都不会影响这个中心点的情况。

Code#

1
// Problem: 迷宫
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1114/
4
// Time: 2026-03-29 22:32:50
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 110;
8

9
int n, m, xa, ya, xb, yb;
10
char g[N][N];
11
bool st[N][N];
12
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
13

14
bool dfs(int a, int b)
15
{
16
    if (g[a][b] == '#')
17
        return false;
18
    if (a == xb && b == yb)
19
        return true;
20

21
    st[a][b] = true;
22

23
    for (int i = 0; i < 4; i++)
24
    {
25
        int x = a + dx[i], y = b + dy[i];
26
        if (x >= 0 && x < n && y >= 0 && y < n && !st[x][y] && dfs(x, y))
27
            return true;
28
    }
29
    return false;
30
}
31

32
void solve()
33
{
34
    cin >> n;
35
    for (int i = 0; i < n; i++)
36
        for (int j = 0; j < n; j++)
37
            cin >> g[i][j];
38
    cin >> xa >> ya >> xb >> yb;
39

40
    memset(st, false, sizeof st);
41

42
    if (dfs(xa, ya))
43
        cout << "YES" << endl;
44
    else
45
        cout << "NO" << endl;
46
}
47

48
int main()
49
{
50
    int T;
51
    cin >> T;
52
    while (T--)
53
        solve();
54
    return 0;
55
}

红与黑-Flood Fill#

由于搜索的所有点都在棋盘内，因此不需要恢复现场。注意本题的特殊输入，每次输入图后需要重置 st 数组为 0

Code#

1
// Problem: 红与黑
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1115/
4
// Time: 2026-03-31 21:15:15
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 25;
8

9
int n, m;
10
char g[N][N];
11
bool st[N][N];
12

13
int dx[4] = {-1, 0, 0, 1};
14
int dy[4] = {0, -1, 1, 0};
15

16
int dfs(int a, int b)
17
{
18
    int res = 1;
19
    st[a][b] = true;
20
    for (int i = 0; i < 4; i++)
21
    {
22
        int x = a + dx[i], y = b + dy[i];
23
        if (x < 0 || x >= n || y < 0 || y >= m)
24
            continue;
25
        if (g[x][y] != '.')
26
            continue;
27
        if (st[x][y])
28
            continue;
29

30
        res += dfs(x, y);
31
    }
32
    return res;
33
}
34

35
int main()
36
{
37
    while (cin >> m >> n, n || m)
38
    {
39
        for (int i = 0; i < n; i++)
40
            for (int j = 0; j < m; j++)
41
                cin >> g[i][j];
42

43
        int stx, sty;
44
        for (int i = 0; i < n; i++)
45
            for (int j = 0; j < m; j++)
46
                if (g[i][j] == '@')
47
                    stx = i, sty = j;
48

49
        memset(st, 0, sizeof st);
50
        cout << dfs(stx, sty) << endl;
51
    }
52
    return 0;
53
}

搜索顺序#

搜索顺序主要是递归搜索树的扩展方式，通过不同的顺序规划完成不重不漏或优化的效果。

马走日#

dfs 模板题，注意处理多组输入和搜索时恢复现场。

Code#

1
// Problem: 马走日
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1118/
4
// Time: 2026-03-31 21:39:29
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 10;
8

9
int n, m;
10
bool st[N][N];
11
int res;
12
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
13
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
14

15
void dfs(int x, int y, int cnt)
16
{
17
    if (cnt == n * m)
18
    {
19
        res++;
20
        return;
21
    }
22

23
    st[x][y] = true;
24

25
    for (int i = 0; i < 8; i++)
26
    {
27
        int a = x + dx[i], b = y + dy[i];
28
        if (a < 0 || a >= n || b < 0 || b >= m)
29
            continue;
30
        if (st[a][b])
31
            continue;
32
        dfs(a, b, cnt + 1);
33
    }
34

35
    st[x][y] = false;
36
}
37

38
int main()
39
{
40
    int T;
41
    cin >> T;
42
    while (T--)
43
    {
44
        int x, y;
45
        cin >> n >> m >> x >> y;
46

47
        memset(st, false, sizeof st);
48
        res = 0;
49

50
        dfs(x, y, 1);
51
        cout << res << endl;
52
    }
53
    return 0;
54
}

单词接龙#

Code#

1
// Problem: 单词接龙
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1119/
4
// Time: 2026-04-02 12:51:16
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 21;
8

9
int n, res;
10
string word[N];
11
int g[N][N]; // 若单词之间可以拼接，存储他们前缀和后缀公共部分的最小值
12
int used[N]; // 记录某个单词被使用的次数
13

14
void dfs(string dragon, int last) // dfs传入当前的龙和上一次使用的单词
15
{
16
    res = max((int) dragon.size(), res);
17
    used[last]++;
18

19
    for (int i = 0; i < n; i++)
20
        if (g[last][i] && used[i] < 2)
21
            dfs(dragon + word[i].substr(g[last][i]), i);
22

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

26
int main()
27
{
28
    cin >> n;
29
    for (int i = 0; i < n; i++)
30
        cin >> word[i];
31

32
    char start;
33
    cin >> start;
34

35
    // 枚举所有单词对，判断是否可以拼接
36
    for (int i = 0; i < n; i++)
37
        for (int j = 0; j < n; j++)
38
        {
39
            string a = word[i], b = word[j];
40
            for (int k = 1; k < (int) min(a.size(), b.size()); k++)
41
            {
42
                if (a.substr(a.size() - k) == b.substr(0, k))
43
                {
44
                    g[i][j] = k;
45
                    break;
46
                }
47
            }
48
        }
49

50
    for (int i = 0; i < n; i++)
51
    {
52
        if (word[i][0] == start)
53
            dfs(word[i], i);
54
    }
55

56
    cout << res << endl;
57
    return 0;
58
}

分成互质组#

思路#

为了保证搜索树的分支较小，所以我们按组枚举。按照下标从小到大的顺序搜索每个数且 st[] 判重，以达到不重不漏的搜索效果（按照组合型枚举的顺序）。

那么对于每个数，只有两种选择：放入此时的最后一组或新开一个组放入

根据贪心思想，如果一个数可以放进最后一组内，那么一定不用新开一个组来放

Code#

1
// Problem: 分成互质组
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1120/
4
// Time: 2026-04-02 15:21:02
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 10;
8

9
int n, res; // res为当前所存在的最优解
10
int p[N]; // 存放数
11
int group[N][N]; // 存放每个组
12
bool st[N]; // 标记每个数是否被放进了组内
13

14
bool check(int g[], int gc, int num)
15
{
16
    for (int i = 0; i < gc; i++)
17
    {
18
        if (gcd(g[i], p[num]) > 1) // 只要组内有数和该数不互质了，就 return false
19
            return false;
20
    }
21
    return true;
22
}
23

24
void dfs(int g, int gc, int tc, int start)
25
// g为当前的最后一组的组的序号, gc为当前组内搜索到的数的序号；
26
// tc为当前搜索过的数的数量, start为当前组开始搜索的数的序号。
27
{
28
    if (g >= res) // 如果有比当前最优解所需的组数更多的解法，说明此解不为最优解
29
        return;
30

31
    if (tc == n) // 如果搜完了所有点,说明此解为当前的最优解,更新最优解
32
        res = g;
33

34
    bool flag = true; // 标记能否可以新开一组
35

36
    for (int i = start; i < n; i++) // 枚举每个数
37
    {
38
        if (!st[i] && check(group[g], gc, i)) // 如果当前数还未被放进组里且与当前的组中的数都互质
39
        {
40
            // 将该数放进该组
41
            st[i] = true;
42
            group[g][gc] = p[i];
43

44
            // 继续搜索该组,组内数的数量gc + 1,总的数的数量tc + 1,搜索的数的序号i + 1
45
            dfs(g, gc + 1, tc + 1, i + 1);
46

47
            // 恢复现场
48
            st[i] = false;
49

50
            // 如果能放进当前最后一组,则不用新开一组,故flag标记为false
51
            flag = false;
52
        }
53
    }
54

55
    // 如果无法放进最后一组,则新开一组来搜索
56
    if (flag)
57
        dfs(g + 1, 0, tc, 0);
58
}
59

60
int main()
61
{
62
    cin >> n;
63
    res = n; // 还未搜索时,假定最优解为最坏的情况每个数都分一组
64
    for (int i = 0; i < n; i++)
65
        cin >> p[i];
66

67
    dfs(1, 0, 0, 0);
68
    cout << res << endl;
69
    return 0;
70
}

剪枝与优化#

常用的优化策略有以下几种：

优化搜索顺序：大部分情况下，我们应该优先搜索分支较少的节点

排除等效冗余：不考虑顺序的话，尽量用组合式的方式搜索

可行性剪枝：搜到一半发现不合法的时候，提前退出

最优性剪枝：当前搜索状态比全局的值还差的时候，提前退出

记忆化搜索：类似动态规划

小猫爬山#

从前往后枚举每一个小猫，每一次枚举当前小猫放到哪个车上，dfs(u, k) 表示 u 只小猫，用 k 个车的情况。

如果可以放在已有的车上，就放进去，即 dfs(u + 1, k)

否则新开一个车来放猫，即 dfs(u + 1, k + 1)

board3

Code#

1
// Problem: Luogu P10483
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P10483
4
// Time: 2026-04-13 17:19:47
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 20;
8

9
int n, m, ans = 20;
10
int w[N], sum[N];
11

12
void dfs(int u, int k)
13
{
14
    if (k >= ans)
15
        return;
16

17
    if (u == n)
18
    {
19
        ans = k;
20
        return;
21
    }
22

23
    for (int i = 0; i < k; i++)
24
    {
25
        if (sum[i] + w[u] <= m)
26
        {
27
            sum[i] += w[u];
28
            dfs(u + 1, k);
29
            sum[i] -= w[u];
30
        }
31
    }
32

33
    sum[k] = w[u];
34
    dfs(u + 1, k + 1);
35
    sum[k] = 0;
36
}
37

38
int main()
39
{
40
    cin >> n >> m;
41

42
    for (int i = 0; i < n; i++)
43
        cin >> w[i];
44

45
    sort(w, w + n, greater<int>());
46

47
    dfs(0, 0);
48

49
    cout << ans << endl;
50
    return 0;
51
}