第十章 搜索与回溯

有些题目要求列出所有方案，有些题目只问能否到达目标，还有些题目要求最少走几步。这些任务都可以从一个初始状态出发，按允许的选择逐步扩展，但保存状态和处理重复的方式并不相同。

本章先用排列、组合和皇后放置建立深度优先搜索（DFS）与回溯，再用迷宫路径说明为什么有的访问标记必须恢复。随后从骑士遍历推导广度优先搜索（BFS），并把同一遍历思想用于网格连通块。剪枝放在完整搜索过程之后讨论：只有说明某个分支为何不可能提供所需的新结果，才能安全地跳过它。

阅读前需要掌握第七章的递归以及第九章的队列。递归负责保存“这一层还没做完什么”，搜索则进一步规定每层可以尝试哪些选择。本章的网格可以直接由坐标求相邻位置；一般图的存储将在下一章介绍。

各节代码按 C++17 编写，省略共同的 #include <bits/stdc++.h>、using namespace std; 和输入输出主函数。它们是独立的搜索核心，不能把同名的全局数组和函数直接拼进一个程序。文中说明了数据范围、初始化和调用方式，配套核验程序会从本文提取代码并补齐输入输出后编译。网格除特别说明外按行、列从 $1$ 开始编号，行向下增加，列向右增加。

1. 从全排列建立搜索状态

任务：把 $1$ 至 $n$ 每个整数使用一次，输出所有排列。先看 $n=3$。第一个位置可以填 $1,2,3$；如果第一个位置填了 $1$，第二个位置就只能填 $2$ 或 $3$。每确定一个位置，问题就变成“在剩余整数中填写后面的位置”。

直接使用 $n$ 层循环并不适合变化的 $n$。递归可以让第 $u$ 层负责填写第 $u$ 个位置。只保存当前层数还不够：同样准备填写第二个位置，前面用了 $1$ 和前面用了 $2$，可选整数不同。因此还需要记录已经使用的整数。

令 $a[u]$ 表示第 $u$ 个位置填写的数，$used[x]$ 表示整数 $x$ 是否已在当前排列前缀中使用。先只走以 $1$ 开头的部分：第二个位置先试 $2$，第三个位置只剩 $3$，于是输出 $(1,2,3)$。输出之后并没有完成全部任务，第二个位置还没有试过 $3$。

递归返回时，需要回到当初调用下一层的位置。调用 dfs(4) 的是填写第三位的 dfs(3)；它继续执行调用后面的语句，取消数字 $3$ 的标记。第三位没有其他未用数字后，dfs(3) 才返回 dfs(2)，让第二位取消数字 $2$ 的标记，再尝试 $3$。这个“选择、深入、撤销”的过程就是回溯。

正在发生的事	执行所在层	有效前缀	used 中为真的数字	本层接下来做什么
第一位选 $1$	dfs(1)	$(1)$	$1$	进入 dfs(2)
第二位选 $2$	dfs(2)	$(1,2)$	$1,2$	进入 dfs(3)
第三位选 $3$	dfs(3)	$(1,2,3)$	$1,2,3$	进入 dfs(4) 输出
输出后返回，撤销 $3$	dfs(3)	$(1,2)$	$1,2$	第三位的循环结束，返回
撤销 $2$	dfs(2)	$(1)$	$1$	第二位继续试 $3$
第二位选 $3$	dfs(2)	$(1,3)$	$1,3$	进入新的 dfs(3)
第三位选 $2$	dfs(3)	$(1,3,2)$	$1,2,3$	进入 dfs(4) 输出

图中蓝色边表示向下一层作出选择，橙色虚线表示递归返回。返回到第二位时，第一位的 $1$ 仍然保留，只有属于刚结束分支的标记被撤销。右侧列出关键时刻的有效前缀和标记，与上表使用同一组数据。逐步播放回溯过程可以观察每次变化，静态图和表格保留完整的关键步骤。

下面是完整的搜索核心。数组下标从 $1$ 开始；为使输出规模可控，本例取 $1\le n\le9$，a[25] 和 used[25] 均足够。读入 $n$ 后调用 dfs(1)，全局 used 初始为假。若在同一进程处理多组数据，开始每组前重新清空标记。

int n, a[25];
bool used[25];

void dfs(int u)
{
    // 前 u-1 个位置已确定，越过末位时得到一个完整排列
    if (u > n)
    {
        for (int i = 1; i <= n; ++i)
        {
            cout << a[i] << (i == n ? '\n' : ' ');
        }
        return;
    }

    for (int x = 1; x <= n; ++x)
    {
        if (used[x])
        {
            continue;
        }
        a[u] = x;
        used[x] = true;
        dfs(u + 1);
        used[x] = false;
    }
}

进入 dfs(u) 时，$a[1],\ldots,a[u-1]$ 是互不相同的已填整数，$used$ 恰好标记这些整数。选择未使用的 $x$ 后，这个性质对下一层仍成立；撤销标记后，下一次循环又面对原来的前缀。$a[u]$ 会在下一次选择时被覆盖，且只在完整排列时读取，所以不用清零。

每个排列都有唯一的逐位选择顺序，因而会到达一次叶子；所有合法排列都能由这些选择得到。若从小到大尝试 $x$，输出也按字典序排列。第一位有 $n$ 种选择，第二位有 $n-1$ 种，依次相乘得到 $n\times(n-1)\times\cdots\times1$ 个排列，这个乘积记为 $n!$，读作“$n$ 的阶乘”。输出每个排列需要 $O(n)$ 时间，因此总时间至少为 $O(n\cdot n!)$；数组和递归栈占 $O(n)$ 空间。具体题目的输出规模也应先估算。

递归函数的参数 u 属于各自的调用，下一层得到的是 u+1，不会把上一层的 u 改掉。全局数组 used 却由所有调用共享，递归返回不会自动把它还原。a[u] 留下的旧值也没有消失，但它已经不属于有效前缀；下一次填写会覆盖它，输出又只发生在全部位置都重新确定以后。

这时再抽象搜索问题，几个问题才有了具体含义：状态记录当前前缀及已用整数，选择是下一个位置填什么，终止条件是 $u>n$，重复控制由 $used$ 完成。换一道题时，这四部分需要重新定义，不能只替换函数名。

2. 组合：用递增顺序消除重复

任务：从 $1$ 至 $n$ 中选择 $r$ 个不同整数，每组只输出一次，并按字典序输出。$n=4,r=2$ 时，$(1,2)$ 与 $(2,1)$ 表示同一组；直接沿用全排列搜索会重复。

每组整数都可以唯一地写成严格递增序列。于是填写下一位时，只允许选择大于上一位的数。仍以 $n=4,r=2$ 为例：第一位选 $1$ 后，第二位依次尝试 $2,3,4$；第一位选 $2$ 后，只尝试 $3,4$。第一位选 $4$ 时已经没有足够的数，可以提前结束这一支。

现在把例子改成 $n=5,r=3$，且第一位已经选了 $1$。准备填第二位时，还需要填第二、三位这两个位置。若第二位选 $4$，后面还有 $5$，数量刚好足够；若第二位选 $5$，第三位就没有数可选。

第二位候选 $x$	比它大的数	后面还需 $1$ 个	是否继续
$2$	$3,4,5$	足够	继续
$3$	$4,5$	足够	继续
$4$	$5$	刚好	继续
$5$	无	不足	不必进入下一层

令 dfs(u,last) 负责填写第 $u$ 个位置，last 是上一位选中的整数。当前共需填写 $r-u+1$ 位；选好本位的 $x$ 后，剩下 $r-u$ 位，而比 $x$ 大的数共有 $n-x$ 个。要能填完，必须满足

$$n-x\ge r-u,\qquad x\le n-(r-u).$$

下界 $last+1$ 保证递增，上界 $n-(r-u)$ 保证数量足够。后一个条件就是一次提前排除失败分支，后面会把这类做法称为剪枝。本例限制 $1\le r\le n\le20$，数组 a[25] 足够，输出所有组合前仍应估算输出量。

int n, r, a[25];

void dfs(int u, int last)
{
    if (u > r)
    {
        for (int i = 1; i <= r; ++i)
        {
            cout << a[i] << (i == r ? '\n' : ' ');
        }
        return;
    }

    // 选择 x 后，必须还能留下 r-u 个更大的数
    for (int x = last + 1; x <= n - (r - u); ++x)
    {
        a[u] = x;
        dfs(u + 1, x);
    }
}

从 dfs(1,0) 开始。每次选择都比上一位大，所以不会输出同一集合的不同排列；反过来，每个大小为 $r$ 的集合都有唯一的递增写法，因此不会漏解。不同题目可能另有输出宽度要求，提交时按其题面调整。这里规定相邻数用一个空格分隔。

这段代码没有 used：严格递增已经保证不重复选同一个整数。last 按值传入，下一层接收所选的 x，返回后当前层的 last 仍是原来的值。答案槽 a[u] 会被下一次选择覆盖，也不用清零。

$\binom nr$ 表示从 $n$ 个不同元素中取出 $r$ 个、不计选择顺序的组合数。本节有这么多个完整方案，每组输出 $r$ 个数，输出代价为 $O\!\left(r\binom nr\right)$。搜索还会经过未完成的递增前缀；若只需计数而不输出，不能直接把输出代价当成全部计算代价。递归深度与保存的组合长度都是 $O(r)$。

3. 皇后放置：在扩展前检查约束

组合用递增顺序去掉了同一集合的不同写法。另一类题没有这样的重复，却需要在每一步检查局部约束。以 $n$ 皇后为例：在 $n\times n$ 棋盘放置 $n$ 枚皇后，使任意两枚不在同一行、同一列或同一条对角线上。要求输出前三组按行记录列号的方案，并统计所有方案。

按格子逐个决定放或不放会产生大量不可能达到“每行恰好一枚”的分支。改为一层处理一行，当前行只选择一个列号。这样同行冲突自动消失，只需判断列与两种对角线。

先把“同一条对角线”变成可以检查的量。在棋盘上沿右下方向走一格，行号和列号都加 $1$，所以两者的差不变；沿左下方向走一格，行号加 $1$、列号减 $1$，所以两者的和不变。第 $u$ 行、第 $x$ 列的格子便可以用 $u-x$、$u+x$ 标识两种斜线。

左图蓝色格沿右下方向排列，行列差均为 $0$；橙色格沿左下方向排列，行列和均为 $5$。它们不是额外限制，而是把同一斜线上的格子归到同一编号。右图已经放置 $(1,2)$、$(2,4)$ 两枚皇后，第三行只剩第 $1$ 列合法：第 $2,4$ 列与已有皇后同列，第 $3$ 列与 $(2,4)$ 同在行列和为 $6$ 的斜线上。

继续在第四行试列，选第 $3$ 列得到方案 $(2,4,1,3)$。输出以后撤销第四行对列 $3$ 和两条斜线的占用，再继续本层循环；这一层没有其他合法列，才回到第三行撤销列 $1$。因此棋盘也有与排列相同的“选择—深入—撤销”过程，只是一次选择同时改变三类标记。

行列差可能为负，不能直接作为数组下标。行列编号均在 $1$ 至 $n$ 时，$u-x$ 在 $1-n$ 至 $n-1$ 之间。统一加 $n$ 后，编号落在 $1$ 至 $2n-1$；行列和则在 $2$ 至 $2n$ 之间。加上相同常数不会改变两个差值是否相等，因此不会改变冲突判断。

令 col[x]、d1[u+x]、d2[u-x+n] 表示当前前缀是否占用相应的列或对角线。$a[u]$ 保存第 $u$ 行列号，$ans$ 记录完整方案数。以下取 $1\le n\le13$，数组能覆盖上述编号；所有标记和 ans 初始为零，从 dfs(1) 开始。

int n, a[15], ans;
bool col[15], d1[30], d2[30];

void dfs(int u)
{
    if (u > n)
    {
        ++ans;
        if (ans <= 3)
        {
            for (int i = 1; i <= n; ++i)
            {
                cout << a[i] << ' ';
            }
            cout << '\n';
        }
        return;
    }

    for (int x = 1; x <= n; ++x)
    {
        int s = u + x, d = u - x + n;
        if (col[x] || d1[s] || d2[d])
        {
            continue;
        }
        a[u] = x;
        col[x] = d1[s] = d2[d] = true;
        dfs(u + 1);
        col[x] = d1[s] = d2[d] = false;
    }
}

每层只放一枚皇后，且在递归前排除与已有皇后冲突的列和对角线，所以到达叶子的一定是合法布局。任何合法布局在每一行都有确定的列号，搜索会沿唯一的一条分支到达它。从小到大尝试列号，完整方案便按列号序列的字典序出现。只输出前三组不等于只搜索前三组，否则 $ans$ 不再是总方案数。

仅按列去重时，完整候选至多有 $n!$ 个；对角线检查还会提前排除部分前缀。若把每层最多 $n$ 次列检查计入，一个直接的时间上界为 $O(n\cdot n!)$，实际搜索量取决于约束。标记数组及递归栈使用 $O(n)$ 空间。

4. 迷宫路径：区分当前路径与全局访问

皇后搜索的标记只描述当前放置前缀，返回上层时必须撤销。网格里的访问标记也可能具有同样的含义。考虑一个至多 $5\times5$ 的迷宫：从起点到终点，每次上下左右走一格，每个格子在同一条路径中最多经过一次，求不同路径数。

先用没有障碍的 $2\times3$ 网格，从左上角 $S$ 到右下角 $T$。给其他格子临时起名，便于描述路线：

S A B
C D T

其中两条合法路线是 $S\to A\to D\to T$ 和 $S\to C\to D\to A\to B\to T$。两次到达 $A$，位置虽然相同，已经走过的格子却不同：第一条路线刚走到 $A$ 时，$D$ 还能走；第二条路线走到 $A$ 时，$D$ 已经在当前路径中，不能再走。

图中橙色表示当前路径已经经过的格子，蓝框表示当前位置 $A$。蓝色箭头标出可继续选择的方向；两幅图中的可走集合不同。因此“到过 $A$”不足以决定后续过程，还必须知道这次沿途用过哪些格子。

按下面代码的上、下、左、右顺序搜索，先得到 $S\to C\to D\to A\to B\to T$，再得到 $S\to C\to D\to T$。返回 $S$ 后，还应继续尝试从 $S$ 到 $A$，得到另两条路径，总计 $4$ 条。若已离开的格子仍永久标记，$A$ 会被第一条路线占住，最后只能数到 $2$ 条。这里导致漏解的是中间格 $A$ 的标记，不是终点的标记。

这里 $used[x][y]$ 的确切含义是“格子 $(x,y)$ 已出现在当前递归路径上”。对需要继续扩展的格子，进入时标记，离开当前递归分支时撤销。终点是提前结算的情况：到达就返回一条路径，不继续扩展，也不设置标记。设障碍由 $wall$ 标记，起点和终点都不是障碍，从起点调用 dfs(sx,sy)：

int n, m, fx, fy;
bool wall[6][6], used[6][6];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

long long dfs(int x, int y)
{
    if (x == fx && y == fy)
    {
        return 1;
    }

    used[x][y] = true;
    long long ways = 0;
    for (int k = 0; k < 4; ++k)
    {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > n || ny < 1 || ny > m)
        {
            continue;
        }
        if (wall[nx][ny] || used[nx][ny])
        {
            continue;
        }
        ways += dfs(nx, ny);
    }
    used[x][y] = false;
    return ways;
}

每次递归只走向尚未出现在当前路径中的格子，因此路径不会重复格子。任意合法路径的每一步都能在对应方向被尝试，且它的坐标序列唯一，所以恰好计数一次。起点等于终点时，函数直接返回 $1$，表示长度为零的一条路径。

这里即使两条路径到达同一个格子，后续可走范围也可能不同，因为各自已经走过的格子不同。只把坐标当作全局状态并永久判重，会丢失合法路径。最多经过 $nm$ 个格子，递归栈和路径标记需要 $O(nm)$ 空间；路径数量与搜索结点数随网格变化迅速，不能把这类路径枚举写成 $O(nm)$ 时间。本例使用 long long 保存条数。路径至多有 $24$ 步，首步至多四种选择，以后不能立即走回上一步，因此每步至多三种选择；所有候选前缀数不超过 $1+4\sum_{j=0}^{23}3^j=2\cdot3^{24}-1$，仍在 long long 范围内。这个上界很宽松，但足以说明计数类型安全。换成更大网格时，时间和计数类型都要重新检查。

5. 骑士遍历：按步数逐层扩展

现在换一个目标：在 $n\times m$ 棋盘上，求骑士从起点到每个格子的最少步数，不可达输出 $-1$。深度优先搜索找到的第一条路线不一定最短；若枚举所有路线再取最小值，同一格子又会被大量重复处理。

每次骑士移动都恰好增加一步。于是可以先处理距离为 $0$ 的起点，再处理一步可达的格子，随后处理两步可达的格子。队列按发现顺序保存格子，正好维持这个层次。

在 $3\times3$ 棋盘从 $(1,1)$ 出发，一步只能到 $(2,3)$ 和 $(3,2)$，两步新发现 $(3,1)$ 和 $(1,3)$。继续按照队列顺序处理，会出现下面的过程。表中的“新发现”排除了越界和已经发现的格子。

刚出队的格子	它的距离	本次新发现	操作后的队列（从队首到队尾）
尚未出队	—	起点 $(1,1)$	$(1,1)$
$(1,1)$	$0$	$(2,3),(3,2)$	$(2,3),(3,2)$
$(2,3)$	$1$	$(3,1)$	$(3,2),(3,1)$
$(3,2)$	$1$	$(1,3)$	$(3,1),(1,3)$
$(3,1)$	$2$	$(1,2)$	$(1,3),(1,2)$
$(1,3)$	$2$	$(2,1)$	$(1,2),(2,1)$
$(1,2)$	$3$	$(3,3)$	$(2,1),(3,3)$
$(2,1)$	$3$	无；$(3,3)$ 已发现	$(3,3)$
$(3,3)$	$4$	无	空

图中格内数字是距离，中心的 $-1$ 表示骑士无法到达。蓝色箭头对应第一次发现 $(3,3)$，橙色虚线对应第二次遇到它。处理 $(2,1)$ 时，$(3,3)$ 还没有出队，但已经在队列中；若等出队才标记，它会被再次加入。因此应在入队的同时记录距离。图右侧展示这两步的队列，与表格的后几行对应。

同一距离内按照哪一种方向顺序扫描，可以改变同层的出队次序，却不会让距离为 $2$ 的格子排到尚未处理的距离为 $1$ 的格子前面。队首到队尾的距离始终不下降，最多同时保留相邻两个距离层。

令 $dis[x][y]$ 初始为 $-1$。发现一个新格子时立即设定距离并入队。这样即使多个前驱都能到达它，也只会入队一次。以下代码用 queue<pair<int,int>> 保存格子：一对整数依次记录行、列，q.push({x,y}) 把一个坐标放到队尾。C++17 的 auto [x,y] = q.front() 把队首坐标的两个分量分别复制到局部变量 x,y，随后 q.pop() 才把队首移除。dis 的容量覆盖 $1\le n,m\le400$；读入尺寸和起点后调用 bfs()，最后按行输出距离数组。

int n, m, sx, sy, dis[405][405];
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

void bfs()
{
    memset(dis, -1, sizeof(dis));
    queue<pair<int, int>> q;
    dis[sx][sy] = 0;
    q.push({sx, sy});

    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 8; ++k)
        {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m)
            {
                continue;
            }
            if (dis[nx][ny] != -1)
            {
                continue;
            }
            dis[nx][ny] = dis[x][y] + 1;
            q.push({nx, ny});
        }
    }
}

起点是第 $0$ 层。假设距离为 $d$ 的格子都已按层入队，从它们发现的新格子距离为 $d+1$，并排在原队列后面。因此第一次发现某格时，不可能还存在一条尚未处理、步数更少的路线；$dis$ 就是最短步数。每格最多入队一次，每次检查八种移动，时间与空间复杂度均为 $O(nm)$。这个证明依赖每次移动的代价相同；代价不同的最短路不能直接使用此结论。

比较前两种访问标记：迷宫路径的 $used$ 描述一条正在形成的路线，返回时恢复；骑士遍历的 $dis$ 描述从起点已求出的最短距离，首次发现后永久保留。标记能否恢复，取决于它代表的是当前分支的信息，还是所有分支共享的结果。

6. 网格连通块：一次搜索覆盖一个区域

求最短步数只是按层遍历的一种用途。若只想知道哪些格子互相连通，从一个未访问的合法格子出发，用 DFS 或 BFS 扩展所有能走到的格子，都可以找到一个连通块。

考虑数字网格：字符 0 表示空白，1 至 9 表示细胞部分；上下左右相邻的非零格属于同一个细胞。求细胞数量。下面的例子有三个细胞：

11000
01010
00010
10000

前两行左侧的三个非零格互相连通；右侧两格构成第二块；左下角单独构成第三块。逐格扫描时，每遇到一个未访问的非零格，就把答案加一，并从它出发标记整块。之后再扫描到这一块中的其他格子，不会重复计数。

外层逐行扫描和内部搜索分工不同：外层寻找尚未归入任何已发现区域的格子；一旦找到，内部搜索就一次处理整个区域。对于这张图，过程是：

外层遇到的位置	是否启动搜索	搜索完成后的新标记	$cnt$
$(1,1)$	是	$(1,1),(1,2),(2,2)$	$1$
$(1,2)$、$(2,2)$	否，已标记	不变	$1$
$(2,4)$	是	$(2,4),(3,4)$	$2$
$(3,4)$	否，已标记	不变	$2$
$(4,1)$	是	$(4,1)$	$3$

这里的 vis 表示“已经被某次区域搜索发现”，发现时立刻置真并入队，而不是等整块搜索结束再标记。外层扫描只在一次 fill 完全结束后继续，因此看到某个已标记格时，它所在的块已经全部处理过。标记要在整次扫描中保留，否则同一块会被重复计数。

以下使用队列避免长条形区域造成过深递归；取 $1\le n,m\le100$，a 为已读入的字符网格，下标从 $1$ 开始。

int n, m;
char a[105][105];
bool vis[105][105];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void fill(int sx, int sy)
{
    queue<pair<int, int>> q;
    vis[sx][sy] = true;
    q.push({sx, sy});

    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k)
        {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m)
            {
                continue;
            }
            if (a[nx][ny] == '0' || vis[nx][ny])
            {
                continue;
            }
            vis[nx][ny] = true;
            q.push({nx, ny});
        }
    }
}

int count_cells()
{
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (a[i][j] != '0' && !vis[i][j])
            {
                ++cnt;
                fill(i, j);
            }
        }
    }
    return cnt;
}

调用 count_cells() 前，$vis$ 应全部为假。一次 fill 只会进入同一连通块的格子，并且能沿相邻关系到达该块中的每个格子；所以每个连通块恰好让 $cnt$ 增加一次。每格至多入队一次，时间与空间上界都是 $O(nm)$。

若题目规定斜向相邻也算连通，就需要改为八个方向。两个只在角上接触的格子，在四方向规则下分属两块，在八方向规则下属于同一块。方向规则与“哪些格子可走”都必须来自题目，不能只改方向数组而沿用另一题的格子条件。

7. 剪枝：用同一道题逐步减少搜索

回溯枚举的候选可能很多。剪枝是在尚未走到叶子时，证明整个分支都不可能贡献所需答案，于是提前返回。下面用一个具体任务区分几种依据。

给定 $n$ 个非负整数，恰好选 $k$ 个，使总和不超过上限 $L$，求可能的最大总和。若相同数值出现在不同位置，只求最大总和时，这些位置造成的等价选择可以合并。这里规定 $1\le n\le20$、$0\le k\le n$、$0\le L\le10^8$、$0\le a_i\le10^6$。当 $k=0$ 时允许选空集，和值为 $0$；若没有合法方案，输出 $-1$。任意候选和至多 $2\times10^7$，int 足够。若给出更大规模或数值，需重新分析搜索量与整数类型。

本节代码采用从 $0$ 开始的下标，先把数字降序排列为 $a_0\ge a_1\ge\cdots\ge a_{n-1}$，从左到右选择下标递增的 $k$ 个数。令 dfs(start,chosen,sum)：下一次只能从 $start$ 及之后的下标选择；$chosen$ 个数已经选定，当前总和为 $sum$。例如 $[8,6,6,3,1]$、$k=2$、$L=11$，先尝试 $8$，再试 $6$ 得到 $14$，超过上限；改试 $3$ 得到 $11$，已经找到可行答案。

先不考虑额外的剪枝，按递增下标选出恰好 $k$ 个数，到叶子再检查是否超限。下面是独立的基准核心：a 已按降序排列，ans=-1，调用 dfs(0,0,0)。排序还没有删掉任何候选，只改变尝试顺序。

int n, k, limit, a[25], ans = -1;

void dfs(int start, int chosen, int sum)
{
    if (chosen == k)
    {
        if (sum <= limit)
        {
            ans = max(ans, sum);
        }
        return;
    }
    for (int i = start; i < n; ++i)
    {
        dfs(i + 1, chosen + 1, sum + a[i]);
    }
}

这里 start 表示下一候选下标的起点，不是已经选了多少个数；已选个数由 chosen 记录。三个参数按值传入，下一层的 sum+a[i] 不会改掉当前层的 sum，所以函数没有对应的“减回 a[i]”语句。对照先前的搜索，可以把“是否需要撤销”落实到具体读写，而不是看变量是否出现在递归函数里。

保存的量	下一层怎样影响它	返回后怎样处理
排列的全局 used[x]	下一层与当前层读写同一数组	撤销本次选择设置的标记
排列、组合的答案槽 a[u]	后面位置可能留下旧值	下一候选覆盖；只读完整有效前缀
组合的参数 last	下一调用接收所选值的副本	当前调用的参数未变，无需撤销
本节的参数 sum	下一调用接收 sum+a[i]	当前调用的和值未变，无需减回

下面逐项判断哪些尚未完成的分支不必走到叶子。

7.1 可行性：后续无法修复超限

因为所有数字非负，当前 $sum>L$ 后，再加入数字也不可能回到上限之内。这一分支可以直接停止。若未来允许选择负数，同样的判断就不成立。另一个确定的失败条件是剩余数字数目少于还需选择的个数。下标从 $0$ 开始，start 及之后共有 $n-start$ 个数，还需 $need=k-chosen$ 个；若 $n-start<need$，连数量都凑不齐。通过检查以后，本层候选也只需枚举到 $n-need$，理由与组合一节相同。

仍以 $[8,6,6,3,1]$ 为例，先选 $8$ 再选 $6$ 会得到 $14>11$，这支停止。若某个状态只剩最后一个 $1$，却还要选两个数，即使当前和没有超限也应停止。两个条件解决的失败原因不同，不能相互替代。

7.2 最优性：计算安全的乐观上界

设还需选 $need=k-chosen$ 个。忽略上限 $L$，从剩余数字中取最大的 $need$ 个，得到这一分支可能达到的总和上界。若该上界仍不大于已找到的答案 $ans$，这支不可能改善答案，可以跳过。

在上例找到 $11$ 后，若当前分支准备从 $3$ 开始选两个数，最大的总和也只有 $3+1=4$，无需再向下枚举。若当前已选第一个 $6$，还需选一个，剩下最大的数也是 $6$，乐观上界为 $12$；实际 $6+6$ 超过 $L=11$，该分支最佳只能是 $6+3=9$。上界 $12$ 不是承诺能达到 $12$，它只是保证真正答案不会比 $12$ 更大。

上界为何必须乐观，可以另用 $[8,3,1]$、$k=2$、$L=11$ 检查。假设已找到 $9$，当前已选 $8$。若错误地只用剩余最小值 $1$ 补全，就会得到所谓“上界” $9$ 并删除分支，却漏掉 $8+3=11$。剩余最大的 $need$ 个数提供的是所有补全的上界，任意挑一组补全只提供一个候选值。忽略 $L$ 可能把上界估得偏大，这只会使剪枝较弱；若把上界估得偏小，就可能错删真正的最优解。这里仅求最优值，等于 $ans$ 的分支可以跳过；若还要统计最优方案数，则需要保留这些分支。

7.3 顺序与去重：让前两种剪枝更有机会生效

先试较大的数字，往往可以更早得到较大的可行答案，使后续的最优性剪枝更有效。降序本身不保证一定减少搜索结点，真正删除分支的仍是经过证明的条件。

两个 $6$ 若在同一层作为“下一个选中值”，会生成数值相同的后续选择。排序后，在同一层只尝试第一个 $6$；若已经选了第一个 $6$，下一层仍可选择第二个 $6$，因为题目允许选取两份相同数值。这个限制针对同层的等价分支，不是把重复数字从输入中删掉。

图使用 $[8,6_a,6_b,3,1]$、$k=2$、$L=11$。图中的 6a、6b 对应两个带标号的 $6_a$、$6_b$，只是为了辨认输入位置，数值都仍为 $6$。蓝色分支先找到 $8+3=11$；橙色连线和说明表示已经有证明可以停止的分支。根处跳过 $6_b$ 并不删除数列中的第二份 $6$：进入先选 $6_a$ 的下一层后，仍可选择 $6_b$，只是本例它们的和又会被超限条件拒绝。

同层保留较早的相同数值，是因为它后面拥有至少同样多的可选位置。若某个合法数值组合原本从较晚的 $6$ 开始，改为从较早的 $6$ 开始，后续所选位置仍在它之后，和值也不变。因此不会漏掉所需的最大值。若任务改为输出全部下标组合，就不能把这两个位置视为相同。

下面给出加入这些判断后的搜索核心。$a[0],\ldots,a[n-1]$ 已按降序排列，代码中的 $limit$ 保存题目上限 $L$，$ans$ 初始为 $-1$，表示尚无可行方案；调用 dfs(0,0,0)。搜索结束后，若 $ans=-1$，表示不存在满足条件的组合。所有数字及总和若可能超过 int 的范围，应把数组元素、$L$、$ans$ 与 $sum$ 一起改为 long long。

int n, k, limit, a[25], ans = -1;

void dfs(int start, int chosen, int sum)
{
    if (sum > limit)
    {
        return;
    }
    if (chosen == k)
    {
        ans = max(ans, sum);
        return;
    }

    int need = k - chosen;
    if (n - start < need)
    {
        return;
    }

    int upper = sum;
    for (int i = start; i < start + need; ++i)
    {
        upper += a[i];
    }
    if (upper <= ans)
    {
        return;
    }

    for (int i = start; i <= n - need; ++i)
    {
        if (i > start && a[i] == a[i - 1])
        {
            continue;
        }
        dfs(i + 1, chosen + 1, sum + a[i]);
    }
}

当 $chosen=k$ 时，当前和就是一个完整方案；非负性保证超限判断安全。$upper$ 是当前分支中任意补全方案的上界，$upper\le ans$ 时不会错过更大答案。同层去重只删除数值相同的下一选择，留下的分支仍覆盖每一种不同的数值组合。没有任何剪枝时，枚举至多涉及 $O(2^n)$ 个子集结点；代码每个结点至多扫描 $O(n)$ 个候选和上界元素，因此保守时间上界为 $O(n2^n)$，递归深度为 $O(k)$。剪枝改善实际运行量，但不保证改变最坏情况上界。

这四种做法的依据不同：超限由非负性保证；上界由“剩余最大的 $need$ 个数”保证；顺序只是帮助较早得到答案；去重由“相同数值选择在本题中等价”保证。换成输出所有下标组合、允许负数或统计最优方案数的任务，必须分别重新检查这些条件。

8. 进一步模型：沿用已建立的遍历过程

前面的 BFS 已经说明了队列顺序和首次发现的含义。下面分别改变起点数量、需要保存的结果和寻找区域的方向。每种变化仍需说明状态是什么、在什么时刻记录，不能只把函数名换成另一个名称。

8.1 多源 BFS：让所有起点同时位于第零层

考虑一条长度为 $5$ 的直线，位置 $1$、$5$ 同时开始扩散，每分钟向相邻位置走一步。求每个位置最早被碰到的时刻。若分别从两个端点求距离再逐点取较小值，能得到答案；但源点很多时，每个源点都会重新遍历相同的区域。

最早到达只关心哪个源点先碰到某格，无需为每个源点分别保存一份结果。把所有源点一起放在第 $0$ 层，就能按时间统一向外扩展：

操作	队列（队首在左）	已知距离，- 表示未发现
两端一起入队	$1,5$	$0,-,-,-,0$
取出 $1$，发现 $2$	$5,2$	$0,1,-,-,0$
取出 $5$，发现 $4$	$2,4$	$0,1,-,1,0$
取出 $2$，发现 $3$	$4,3$	$0,1,2,1,0$
取出 $4$，遇到已发现的 $3$	$3$	不变

只要所有起点在开始扩展前都入队，队列仍按距离从小到大处理。若只让第一个源点跑完，再把第二个加进去，原先的距离已经占据许多格子，就不能再使用“访问过便跳过”的规则。

下面将同一过程用于 $1\le n,m\le100$ 的四方向网格。g 中 # 表示障碍，其他字符可走；sx[0..tot-1]、sy[0..tot-1] 保存至多 $nm$ 个合法源点坐标。所有数组全局声明，读完网格和源点后调用 bfs()。重复给出同一个源点也只加入一次；没有源点时，所有距离保持 $-1$。

int n, m, tot, sx[10005], sy[10005], dis[105][105];
char g[105][105];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs()
{
    memset(dis, -1, sizeof(dis));
    queue<pair<int, int>> q;
    for (int i = 0; i < tot; ++i)
    {
        int x = sx[i], y = sy[i];
        if (dis[x][y] == -1)
        {
            dis[x][y] = 0;
            q.push({x, y});
        }
    }
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k)
        {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m)
            {
                continue;
            }
            if (g[nx][ny] == '#' || dis[nx][ny] != -1)
            {
                continue;
            }
            dis[nx][ny] = dis[x][y] + 1;
            q.push({nx, ny});
        }
    }
}

距离 $d$ 的格子表示它至少可以由某个源点用 $d$ 步到达。假如还有更早到达的方法，其前驱应该在更早的层被处理，目标也就早已被发现。因此第一次记录的是到最近源点的距离。每格仍只入队一次，总时间和空间都是 $O(nm)$；等代价前提与单源 BFS 相同。

8.2 路径记录：在首次发现时保存前驱

距离只回答走多少步，不能直接给出经过哪些格子。第一次从 $u$ 发现 $v$ 时，除了设置距离，还可以记住“$v$ 是由 $u$ 来的”。把这个前一个格子称为前驱。

例如空的 $2\times3$ 四方向网格，从 $(1,1)$ 到 $(2,3)$，按上、下、左、右顺序扩展，会记录如下的一条前驱链：

格子	距离	首次发现它的前驱
$(1,1)$	$0$	起点，无前驱
$(2,1)$	$1$	$(1,1)$
$(2,2)$	$2$	$(2,1)$
$(2,3)$	$3$	$(2,2)$

先从终点倒着走，得到 $(2,3),(2,2),(2,1),(1,1)$；逆序后才是从起点到终点的路线。每次回退距离都减一，最后一定走到距离为零的起点。其他最短路线也可能存在，但本题只要求一条，保留首次发现的前驱已经足够。

下面给出独立的四方向最短路径核心。范围为 $1\le n,m\le100$，网格 g 中 # 是障碍，起点 (sx,sy) 和终点 (fx,fy) 均可走。调用 bfs() 后调用 print_path()；不可达输出 -1，否则先输出步数，再逐行输出从起点到终点的坐标。px、py 分别保存前驱的行和列，a、b 暂存倒序路线。

int n, m, sx, sy, fx, fy, dis[105][105];
int px[105][105], py[105][105], a[10005], b[10005];
char g[105][105];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs()
{
    memset(dis, -1, sizeof(dis));
    queue<pair<int, int>> q;
    dis[sx][sy] = 0;
    q.push({sx, sy});
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k)
        {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m)
            {
                continue;
            }
            if (g[nx][ny] == '#' || dis[nx][ny] != -1)
            {
                continue;
            }
            dis[nx][ny] = dis[x][y] + 1;
            px[nx][ny] = x;
            py[nx][ny] = y;
            q.push({nx, ny});
        }
    }
}

void print_path()
{
    if (dis[fx][fy] == -1)
    {
        printf("-1\n");
        return;
    }
    int x = fx, y = fy, len = 0;
    while (true)
    {
        a[len] = x;
        b[len++] = y;
        if (x == sx && y == sy)
        {
            break;
        }
        int nx = px[x][y], ny = py[x][y];
        x = nx;
        y = ny;
    }
    printf("%d\n", dis[fx][fy]);
    for (int i = len - 1; i >= 0; --i)
    {
        printf("%d %d\n", a[i], b[i]);
    }
}

前驱与距离在同一次发现中写入，因此前驱边一定对应距离加一的那次移动。不能到终点以后再随便找一个“访问过”的邻居当作前驱，它的距离可能更大。起点等于终点时，先存入起点，再立即结束回退，得到步数为 $0$、只有一个格子的路径；无需读取起点的前驱。BFS 耗时 $O(nm)$，恢复路线最多经过 $nm$ 个格子，数组和队列均占 $O(nm)$ 空间。

8.3 从外部搜索：识别被包围的区域

设网格中 1 为墙，0 为空白，只能通过上下左右相邻的空白移动。要求把无法连到网格外部的空白改为 2。从某个内部空白开始搜索，也可以判断这一块是否碰到边界；但还需暂存整块并等待判断结果。换个方向，只找出“外部能够走到哪些空白”，剩余空白就能直接分类。

下面的 $5\times5$ 网格用墙围住一片空白，其中又放了一格墙。右下角另有一个与外部连通的空白：

11111
10001
10101
10001
11110

被围住的是中心墙周围的八个空白；中心的 1 仍然是墙。右下角的 0 虽然在图中离它们很近，却被墙隔开，只有右下角自身与外部连通。先按四方向连通逐格判断，就不会把“看起来靠近”误当成相连。

图中原网格由粗框圈出，额外的第 $0$ 行、第 $n+1$ 行、第 $0$ 列、第 $m+1$ 列都为空白。蓝色是从外圈可达的空白，橙色是原网格中尚未访问的空白，灰色是墙。额外外圈本身连成一圈，从 $(0,0)$ 一点出发即可接触原网格的所有边界入口；不用为四条边分别启动搜索。

下面代码适用于 $1\le n,m\le100$。原网格存入 a[1..n][1..m]，全局数组其他位置初始为零，恰好形成空白外圈。vis 初始为假，读入后调用 fill()，再输出原范围内的 a。若处理多组网格，需在每次读入前清空整个 a 和 vis，不能留下上次的外圈或标记。

int n, m, a[105][105];
bool vis[105][105];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void fill()
{
    queue<pair<int, int>> q;
    vis[0][0] = true;
    q.push({0, 0});
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k)
        {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx > n + 1 || ny < 0 || ny > m + 1)
            {
                continue;
            }
            if (a[nx][ny] != 0 || vis[nx][ny])
            {
                continue;
            }
            vis[nx][ny] = true;
            q.push({nx, ny});
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (a[i][j] == 0 && !vis[i][j])
            {
                a[i][j] = 2;
            }
        }
    }
}

凡是能连到外部的原空白，都可以把路径接到空白外圈，因而会被这次搜索访问。反过来，被搜索到的原空白都有一条通向外圈的路线，所以不该填充。最后同时检查“原来为空白”和“未访问”，正好选中封闭区域；只检查未访问会把墙也误改成 2。数组须能访问到第 $n+1$ 行和第 $m+1$ 列，时间和空间都是 $O(nm)$。

9. 怎样选择搜索方式

目标	常用过程	访问状态的含义
列出或统计完整方案	DFS 与回溯	当前选择前缀，需要按分支恢复
统计不重复经过格子的路径	DFS 与回溯	当前路径经过的格子，返回时恢复
求等代价移动的最少步数	BFS	已确定的最短距离，首次发现后保留
求连通块数量	DFS 或 BFS	已处理的区域，整次扫描中保留

“判断能否到达”通常两种遍历都可以完成。选择前，应先写清状态包含哪些信息、一步可以转移到哪里、何时结束，以及两个表面相同的状态是否拥有相同的后续选择。DFS 的递归深度可能达到状态数，BFS 的队列也可能同时保存大量状态，都要按题目范围估算空间。

10. 作业

巩固练习

• 全排列问题：逐位选择与现场恢复。
• 迷宫：路径计数与沿当前路径判重。
• 马的遍历：等步长 BFS 与最短距离。
• 求细胞数量：四方向 Flood Fill 与连通块计数。

提高训练

• USACO 1.5·八皇后：列、对角线约束与全部方案计数。
• 填涂颜色：从外部识别封闭区域。
• 血色先锋队：多源 BFS 与最早到达时间。

练习时，先用一句话写出标记数组所表示的事实，再决定它应该在何时设置、何时恢复。这个判断比记住某个 DFS 或 BFS 模板更重要。