第十章:搜索与回溯

有些题目要求列出所有方案,有些题目只问能否到达目标,还有些题目要求最少走几步。这些任务都可以从一个初始状态出发,按允许的选择逐步扩展,但保存状态和处理重复的方式并不相同。
本章先用排列、组合和皇后放置建立深度优先搜索(DFS)与回溯,再用迷宫路径说明为什么有的访问标记必须恢复。随后从骑士遍历推导广度优先搜索(BFS),并把同一遍历思想用于网格连通块。剪枝放在完整搜索过程之后讨论:只有说明某个分支为何不可能提供所需的新结果,才能安全地跳过它。
阅读前需要掌握第七章的递归以及第九章的队列。递归负责保存“这一层还没做完什么”,搜索则进一步规定每层可以尝试哪些选择。本章的网格可以直接由坐标求相邻位置;一般图的存储将在下一章介绍。
各节代码按 C++17 编写。第 1 至第 6 节给出独立的完整程序;第 7、8 节保留用于比较不同搜索方法的核心片段,并说明初始化与调用方式。每段代码使用自己的全局数组和函数,不能直接拼成同一个程序。网格除特别说明外按行、列从 开始编号,行向下增加,列向右增加。
1. 从全排列建立搜索状态
任务:把 至 每个整数使用一次,输出所有排列。先看 。第一个位置可以填 ;如果第一个位置填了 ,第二个位置就只能填 或 。每确定一个位置,问题就变成“在剩余整数中填写后面的位置”。
直接使用 层循环并不适合变化的 。递归可以让第 层负责填写第 个位置。只保存当前层数还不够:同样准备填写第二个位置,前面用了 和前面用了 ,可选整数不同。因此还需要记录已经使用的整数。
令 表示第 个位置填写的数, 表示整数 是否已在当前排列前缀中使用。先只走以 开头的部分:第二个位置先试 ,第三个位置只剩 ,于是输出 。输出之后并没有完成全部任务,第二个位置还没有试过 。
递归返回时,需要回到当初调用下一层的位置。调用 的是填写第三位的 ;它继续执行调用后面的语句,取消数字 的标记。第三位没有其他未用数字后, 才返回 ,让第二位取消数字 的标记,再尝试 。这个“选择、深入、撤销”的过程就是回溯。
| 正在发生的事 | 执行所在层 | 有效前缀 | 中为真的数字 | 本层接下来做什么 |
|---|---|---|---|---|
| 第一位选 | 进入 | |||
| 第二位选 | 进入 | |||
| 第三位选 | 进入 输出 | |||
| 输出后返回,撤销 | 第三位的循环结束,返回 | |||
| 撤销 | 第二位继续试 | |||
| 第二位选 | 进入新的 | |||
| 第三位选 | 进入 输出 |
图中蓝色边表示向下一层作出选择,橙色虚线表示递归返回。返回到第二位时,第一位的 仍然保留,只有属于刚结束分支的标记被撤销。右侧列出关键时刻的有效前缀和标记,与上表使用同一组数据。逐步播放回溯过程可以观察每次变化,静态图和表格保留完整的关键步骤。
下面是完整程序,输入一行整数 ,每行输出一个排列。数组下标从 开始;为使输出规模可控,本例取 , 和 均足够。读入 后调用 ,全局 初始为假。若在同一进程处理多组数据,开始每组前重新清空标记。
#include <bits/stdc++.h>
using namespace std;
int n,a[25];
bool used[25];
void dfs(int u){
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]=1;
dfs(u+1);
used[x]=0;
}
}
int main(){
cin>>n;
dfs(1);
return 0;
}
进入 时, 是互不相同的已填整数, 恰好标记这些整数。选择未使用的 后,这个性质对下一层仍成立;撤销标记后,下一次循环又面对原来的前缀。 会在下一次选择时被覆盖,且只在完整排列时读取,所以不用清零。
每个排列都有唯一的逐位选择顺序,因而会到达一次叶子;所有合法排列都能由这些选择得到。若从小到大尝试 ,输出也按字典序排列。第一位有 种选择,第二位有 种,依次相乘得到 个排列,这个乘积记为 ,读作“ 的阶乘”。输出每个排列需要 时间,因此总时间至少为 ;数组和递归栈占 空间。具体题目的输出规模也应先估算。
递归函数的参数 属于各自的调用,下一层得到的是 ,不会把上一层的 改掉。全局数组 却由所有调用共享,递归返回不会自动把它还原。 留下的旧值也没有消失,但它已经不属于有效前缀;下一次填写会覆盖它,输出又只发生在全部位置都重新确定以后。
这时再抽象搜索问题,几个问题才有了具体含义:状态记录当前前缀及已用整数,选择是下一个位置填什么,终止条件是 ,重复控制由 完成。换一道题时,这四部分需要重新定义,不能只替换函数名。
2. 组合:用递增顺序消除重复
任务:从 至 中选择 个不同整数,每组只输出一次,并按字典序输出。 时, 与 表示同一组;直接沿用全排列搜索会重复。
每组整数都可以唯一地写成严格递增序列。于是填写下一位时,只允许选择大于上一位的数。仍以 为例:第一位选 后,第二位依次尝试 ;第一位选 后,只尝试 。第一位选 时已经没有足够的数,可以提前结束这一支。
现在把例子改成 ,且第一位已经选了 。准备填第二位时,还需要填第二、三位这两个位置。若第二位选 ,后面还有 ,数量刚好足够;若第二位选 ,第三位就没有数可选。
| 第二位候选 | 比它大的数 | 后面还需 个 | 是否继续 |
|---|---|---|---|
| 足够 | 继续 | ||
| 足够 | 继续 | ||
| 刚好 | 继续 | ||
| 无 | 不足 | 不必进入下一层 |
令 负责填写第 个位置, 是上一位选中的整数。当前共需填写 位;选好本位的 后,剩下 位,而比 大的数共有 个。要能填完,必须满足
下界 保证递增,上界 保证数量足够。后一个条件就是一次提前排除失败分支,后面会把这类做法称为剪枝。本例限制 ,数组 足够,输出所有组合前仍应估算输出量。
#include <bits/stdc++.h>
using namespace std;
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;
}
for(int x=last+1;x<=n-(r-u);++x){
a[u]=x;
dfs(u+1,x);
}
}
int main(){
cin>>n>>r;
dfs(1,0);
return 0;
}
程序输入一行 ,从 开始。每次选择都比上一位大,所以不会输出同一集合的不同排列;反过来,每个大小为 的集合都有唯一的递增写法,因此不会漏解。不同题目可能另有输出宽度要求,提交时按其题面调整。这里规定相邻数用一个空格分隔。
这段代码没有 :严格递增已经保证不重复选同一个整数。 按值传入,下一层接收所选的 ,返回后当前层的 仍是原来的值。答案槽 会被下一次选择覆盖,也不用清零。
表示从 个不同元素中取出 个、不计选择顺序的组合数。本节有这么多个完整方案,每组输出 个数,输出代价为 。搜索还会经过未完成的递增前缀;若只需计数而不输出,不能直接把输出代价当成全部计算代价。递归深度与保存的组合长度都是 。
3. 皇后放置:在扩展前检查约束
组合用递增顺序去掉了同一集合的不同写法。另一类题没有这样的重复,却需要在每一步检查局部约束。以 皇后为例:在 棋盘放置 枚皇后,使任意两枚不在同一行、同一列或同一条对角线上。要求输出前三组按行记录列号的方案,并统计所有方案。
按格子逐个决定放或不放会产生大量不可能达到“每行恰好一枚”的分支。改为一层处理一行,当前行只选择一个列号。这样同行冲突自动消失,只需判断列与两种对角线。
先把“同一条对角线”变成可以检查的量。在棋盘上沿右下方向走一格,行号和列号都加 ,所以两者的差不变;沿左下方向走一格,行号加 、列号减 ,所以两者的和不变。第 行、第 列的格子便可以用 、 标识两种斜线。
左图蓝色格沿右下方向排列,行列差均为 ;橙色格沿左下方向排列,行列和均为 。它们不是额外限制,而是把同一斜线上的格子归到同一编号。右图已经放置 、 两枚皇后,第三行只剩第 列合法:第 列与已有皇后同列,第 列与 同在行列和为 的斜线上。
继续在第四行试列,选第 列得到方案 。输出以后撤销第四行对列 和两条斜线的占用,再继续本层循环;这一层没有其他合法列,才回到第三行撤销列 。因此棋盘也有与排列相同的“选择—深入—撤销”过程,只是一次选择同时改变三类标记。
行列差可能为负,不能直接作为数组下标。行列编号均在 至 时, 在 至 之间。统一加 后,编号落在 至 ;行列和则在 至 之间。加上相同常数不会改变两个差值是否相等,因此不会改变冲突判断。
令 、、 表示当前前缀是否占用相应的列或对角线。 保存第 行列号, 记录完整方案数。以下取 ,数组能覆盖上述编号;所有标记和 初始为零,从 开始。
#include <bits/stdc++.h>
using namespace std;
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]=1;
dfs(u+1);
col[x]=d1[s]=d2[d]=0;
}
}
int main(){
cin>>n;
dfs(1);
cout<<ans<<'\n';
return 0;
}
每层只放一枚皇后,且在递归前排除与已有皇后冲突的列和对角线,所以到达叶子的一定是合法布局。任何合法布局在每一行都有确定的列号,搜索会沿唯一的一条分支到达它。从小到大尝试列号,完整方案便按列号序列的字典序出现。只输出前三组不等于只搜索前三组,否则 不再是总方案数。
仅按列去重时,完整候选至多有 个;对角线检查还会提前排除部分前缀。若把每层最多 次列检查计入,一个直接的时间上界为 ,实际搜索量取决于约束。标记数组及递归栈使用 空间。
4. 迷宫路径:区分当前路径与全局访问
皇后搜索的标记只描述当前放置前缀,返回上层时必须撤销。网格里的访问标记也可能具有同样的含义。考虑一个至多 的迷宫:从起点到终点,每次上下左右走一格,每个格子在同一条路径中最多经过一次,求不同路径数。
先用没有障碍的 网格,从左上角 到右下角 。给其他格子临时起名,便于描述路线:
S A B
C D T
其中两条合法路线是 和 。两次到达 ,位置虽然相同,已经走过的格子却不同:第一条路线刚走到 时, 还能走;第二条路线走到 时, 已经在当前路径中,不能再走。
图中橙色表示当前路径已经经过的格子,蓝框表示当前位置 。蓝色箭头标出可继续选择的方向;两幅图中的可走集合不同。因此“到过 ”不足以决定后续过程,还必须知道这次沿途用过哪些格子。
按下面代码的上、下、左、右顺序搜索,先得到 ,再得到 。返回 后,还应继续尝试从 到 ,得到另两条路径,总计 条。若已离开的格子仍永久标记, 会被第一条路线占住,最后只能数到 条。这里导致漏解的是中间格 的标记,不是终点的标记。
这里 的确切含义是“格子 已出现在当前递归路径上”。对需要继续扩展的格子,进入时标记,离开当前递归分支时撤销。终点是提前结算的情况:到达就返回一条路径,不继续扩展,也不设置标记。设障碍由 标记,起点和终点都不是障碍,从起点调用 。完整程序沿用练习《迷宫》的输入格式:首行 ,下一行 ,接着 行障碍坐标,输出路径数:
#include <bits/stdc++.h>
using namespace std;
int n,m,fx,fy;
bool wall[6][6],used[6][6];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
long long dfs(int x,int y){
if(x==fx&&y==fy)return 1;
used[x][y]=1;
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]=0;
return ways;
}
int main(){
int t,sx,sy,x,y;
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
while(t--){
cin>>x>>y;
wall[x][y]=1;
}
cout<<dfs(sx,sy)<<'\n';
return 0;
}
每次递归只走向尚未出现在当前路径中的格子,因此路径不会重复格子。任意合法路径的每一步都能在对应方向被尝试,且它的坐标序列唯一,所以恰好计数一次。起点等于终点时,函数直接返回 ,表示长度为零的一条路径。
这里即使两条路径到达同一个格子,后续可走范围也可能不同,因为各自已经走过的格子不同。只把坐标当作全局状态并永久判重,会丢失合法路径。最多经过 个格子,递归栈和路径标记需要 空间;路径数量与搜索结点数随网格变化迅速,不能把这类路径枚举写成 时间。本例使用 保存条数。路径至多有 步,首步至多四种选择,以后不能立即走回上一步,因此每步至多三种选择;所有候选前缀数不超过 ,仍在 范围内。这个上界很宽松,但足以说明计数类型安全。换成更大网格时,时间和计数类型都要重新检查。
5. 骑士遍历:按步数逐层扩展
现在换一个目标:在 棋盘上,求骑士从起点到每个格子的最少步数,不可达输出 。深度优先搜索找到的第一条路线不一定最短;若枚举所有路线再取最小值,同一格子又会被大量重复处理。
每次骑士移动都恰好增加一步。于是可以先处理距离为 的起点,再处理一步可达的格子,随后处理两步可达的格子。队列按发现顺序保存格子,正好维持这个层次。
在 棋盘从 出发,一步只能到 和 ,两步新发现 和 。继续按照队列顺序处理,会出现下面的过程。表中的“新发现”排除了越界和已经发现的格子。
| 刚出队的格子 | 它的距离 | 本次新发现 | 操作后的队列(从队首到队尾) |
|---|---|---|---|
| 尚未出队 | — | 起点 | |
| 无; 已发现 | |||
| 无 | 空 |
图中格内数字是距离,中心的 表示骑士无法到达。蓝色箭头对应第一次发现 ,橙色虚线对应第二次遇到它。处理 时, 还没有出队,但已经在队列中;若等出队才标记,它会被再次加入。因此应在入队的同时记录距离。图右侧展示这两步的队列,与表格的后几行对应。
同一距离内按照哪一种方向顺序扫描,可以改变同层的出队次序,却不会让距离为 的格子排到尚未处理的距离为 的格子前面。队首到队尾的距离始终不下降,最多同时保留相邻两个距离层。
令 初始为 。发现一个新格子时立即设定距离并入队。这样即使多个前驱都能到达它,也只会入队一次。以下代码用 保存格子:一对整数依次记录行、列, 把一个坐标放到队尾。C++17 的 把队首坐标的两个分量分别复制到局部变量 ,随后 才把队首移除。 的容量覆盖 ;读入尺寸和起点后调用 ,最后按行输出距离数组。
#include <bits/stdc++.h>
using namespace std;
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});
}
}
}
int main(){
cin>>n>>m>>sx>>sy;
bfs();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)printf("%-5d",dis[i][j]);
puts("");
}
return 0;
}
起点是第 层。假设距离为 的格子都已按层入队,从它们发现的新格子距离为 ,并排在原队列后面。因此第一次发现某格时,不可能还存在一条尚未处理、步数更少的路线; 就是最短步数。每格最多入队一次,每次检查八种移动,时间与空间复杂度均为 。这个证明依赖每次移动的代价相同;代价不同的最短路不能直接使用此结论。
比较前两种访问标记:迷宫路径的 描述一条正在形成的路线,返回时恢复;骑士遍历的 描述从起点已求出的最短距离,首次发现后永久保留。标记能否恢复,取决于它代表的是当前分支的信息,还是所有分支共享的结果。
6. 网格连通块:一次搜索覆盖一个区域
求最短步数只是按层遍历的一种用途。若只想知道哪些格子互相连通,从一个未访问的合法格子出发,用 DFS 或 BFS 扩展所有能走到的格子,都可以找到一个连通块。
考虑数字网格:字符 0 表示空白,1 至 9 表示细胞部分;上下左右相邻的非零格属于同一个细胞。求细胞数量。下面的例子有三个细胞:
11000
01010
00010
10000
前两行左侧的三个非零格互相连通;右侧两格构成第二块;左下角单独构成第三块。逐格扫描时,每遇到一个未访问的非零格,就把答案加一,并从它出发标记整块。之后再扫描到这一块中的其他格子,不会重复计数。
外层逐行扫描和内部搜索分工不同:外层寻找尚未归入任何已发现区域的格子;一旦找到,内部搜索就一次处理整个区域。对于这张图,过程是:
| 外层遇到的位置 | 是否启动搜索 | 搜索完成后的新标记 | |
|---|---|---|---|
| 是 | |||
| 、 | 否,已标记 | 不变 | |
| 是 | |||
| 否,已标记 | 不变 | ||
| 是 |
这里的 表示“已经被某次区域搜索发现”,发现时立刻置真并入队,而不是等整块搜索结束再标记。外层扫描只在一次 完全结束后继续,因此看到某个已标记格时,它所在的块已经全部处理过。标记要在整次扫描中保留,否则同一块会被重复计数。
以下使用队列避免长条形区域造成过深递归;取 , 为已读入的字符网格,下标从 开始。
#include <bits/stdc++.h>
using namespace std;
int n,m;
char a[105][105];
bool vis[105][105];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
void fill(int sx,int sy){
queue<pair<int,int>> q;
vis[sx][sy]=1;
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]=1;
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;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>(a[i]+1);
cout<<count_cells()<<'\n';
return 0;
}
调用 前, 应全部为假。一次 只会进入同一连通块的格子,并且能沿相邻关系到达该块中的每个格子;所以每个连通块恰好让 增加一次。每格至多入队一次,时间与空间上界都是 。
若题目规定斜向相邻也算连通,就需要改为八个方向。两个只在角上接触的格子,在四方向规则下分属两块,在八方向规则下属于同一块。方向规则与“哪些格子可走”都必须来自题目,不能只改方向数组而沿用另一题的格子条件。
7. 剪枝:用同一道题逐步减少搜索
回溯枚举的候选可能很多。剪枝是在尚未走到叶子时,证明整个分支都不可能贡献所需答案,于是提前返回。下面用一个具体任务区分几种依据。
给定 个非负整数,恰好选 个,使总和不超过上限 ,求可能的最大总和。若相同数值出现在不同位置,只求最大总和时,这些位置造成的等价选择可以合并。这里规定 、、、。当 时允许选空集,和值为 ;若没有合法方案,输出 。任意候选和至多 , 足够。若给出更大规模或数值,需重新分析搜索量与整数类型。
本节代码采用从 开始的下标,先把数字降序排列为 ,从左到右选择下标递增的 个数。令 :下一次只能从 及之后的下标选择; 个数已经选定,当前总和为 。例如 、、,先尝试 ,再试 得到 ,超过上限;改试 得到 ,已经找到可行答案。
先不考虑额外的剪枝,按递增下标选出恰好 个数,到叶子再检查是否超限。下面是独立的基准核心: 已按降序排列,,调用 。排序还没有删掉任何候选,只改变尝试顺序。
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]);
}
这里 表示下一候选下标的起点,不是已经选了多少个数;已选个数由 记录。三个参数按值传入,下一层的 不会改掉当前层的 ,所以函数没有对应的“减回 ”语句。对照先前的搜索,可以把“是否需要撤销”落实到具体读写,而不是看变量是否出现在递归函数里。
| 保存的量 | 下一层怎样影响它 | 返回后怎样处理 |
|---|---|---|
| 排列的全局 | 下一层与当前层读写同一数组 | 撤销本次选择设置的标记 |
| 排列、组合的答案槽 | 后面位置可能留下旧值 | 下一候选覆盖;只读完整有效前缀 |
| 组合的参数 | 下一调用接收所选值的副本 | 当前调用的参数未变,无需撤销 |
| 本节的参数 | 下一调用接收 | 当前调用的和值未变,无需减回 |
下面逐项判断哪些尚未完成的分支不必走到叶子。
7.1 可行性:后续无法修复超限
因为所有数字非负,当前 后,再加入数字也不可能回到上限之内。这一分支可以直接停止。若未来允许选择负数,同样的判断就不成立。另一个确定的失败条件是剩余数字数目少于还需选择的个数。下标从 开始, 及之后共有 个数,还需 个;若 ,连数量都凑不齐。通过检查以后,本层候选也只需枚举到 ,理由与组合一节相同。
仍以 为例,先选 再选 会得到 ,这支停止。若某个状态只剩最后一个 ,却还要选两个数,即使当前和没有超限也应停止。两个条件解决的失败原因不同,不能相互替代。
7.2 最优性:计算安全的乐观上界
设还需选 个。忽略上限 ,从剩余数字中取最大的 个,得到这一分支可能达到的总和上界。若该上界仍不大于已找到的答案 ,这支不可能改善答案,可以跳过。
在上例找到 后,若当前分支准备从 开始选两个数,最大的总和也只有 ,无需再向下枚举。若当前已选第一个 ,还需选一个,剩下最大的数也是 ,乐观上界为 ;实际 超过 ,该分支最佳只能是 。上界 不是承诺能达到 ,它只是保证真正答案不会比 更大。
上界为何必须乐观,可以另用 、、 检查。假设已找到 ,当前已选 。若错误地只用剩余最小值 补全,就会得到所谓“上界” 并删除分支,却漏掉 。剩余最大的 个数提供的是所有补全的上界,任意挑一组补全只提供一个候选值。忽略 可能把上界估得偏大,这只会使剪枝较弱;若把上界估得偏小,就可能错删真正的最优解。这里仅求最优值,等于 的分支可以跳过;若还要统计最优方案数,则需要保留这些分支。
7.3 顺序与去重:让前两种剪枝更有机会生效
先试较大的数字,往往可以更早得到较大的可行答案,使后续的最优性剪枝更有效。降序本身不保证一定减少搜索结点,真正删除分支的仍是经过证明的条件。
两个 若在同一层作为“下一个选中值”,会生成数值相同的后续选择。排序后,在同一层只尝试第一个 ;若已经选了第一个 ,下一层仍可选择第二个 ,因为题目允许选取两份相同数值。这个限制针对同层的等价分支,不是把重复数字从输入中删掉。
图使用 、、。图中的 6a、6b 对应两个带标号的 、,只是为了辨认输入位置,数值都仍为 。蓝色分支先找到 ;橙色连线和说明表示已经有证明可以停止的分支。根处跳过 并不删除数列中的第二份 :进入先选 的下一层后,仍可选择 ,只是本例它们的和又会被超限条件拒绝。
同层保留较早的相同数值,是因为它后面拥有至少同样多的可选位置。若某个合法数值组合原本从较晚的 开始,改为从较早的 开始,后续所选位置仍在它之后,和值也不变。因此不会漏掉所需的最大值。若任务改为输出全部下标组合,就不能把这两个位置视为相同。
下面给出加入这些判断后的搜索核心。 已按降序排列,代码中的 保存题目上限 , 初始为 ,表示尚无可行方案;调用 。搜索结束后,若 ,表示不存在满足条件的组合。所有数字及总和若可能超过 的范围,应把数组元素、、 与 一起改为 。
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]);
}
}
当 时,当前和就是一个完整方案;非负性保证超限判断安全。 是当前分支中任意补全方案的上界, 时不会错过更大答案。同层去重只删除数值相同的下一选择,留下的分支仍覆盖每一种不同的数值组合。没有任何剪枝时,枚举至多涉及 个子集结点;代码每个结点至多扫描 个候选和上界元素,因此保守时间上界为 ,递归深度为 。剪枝改善实际运行量,但不保证改变最坏情况上界。
这四种做法的依据不同:超限由非负性保证;上界由“剩余最大的 个数”保证;顺序只是帮助较早得到答案;去重由“相同数值选择在本题中等价”保证。换成输出所有下标组合、允许负数或统计最优方案数的任务,必须分别重新检查这些条件。
8. 进一步模型:沿用已建立的遍历过程
前面的 BFS 已经说明了队列顺序和首次发现的含义。下面分别改变起点数量、需要保存的结果和寻找区域的方向。每种变化仍需说明状态是什么、在什么时刻记录,不能只把函数名换成另一个名称。
8.1 多源 BFS:让所有起点同时位于第零层
考虑一条长度为 的直线,位置 、 同时开始扩散,每分钟向相邻位置走一步。求每个位置最早被碰到的时刻。若分别从两个端点求距离再逐点取较小值,能得到答案;但源点很多时,每个源点都会重新遍历相同的区域。
最早到达只关心哪个源点先碰到某格,无需为每个源点分别保存一份结果。把所有源点一起放在第 层,就能按时间统一向外扩展:
| 操作 | 队列(队首在左) | 已知距离,- 表示未发现 |
|---|---|---|
| 两端一起入队 | ||
| 取出 ,发现 | ||
| 取出 ,发现 | ||
| 取出 ,发现 | ||
| 取出 ,遇到已发现的 | 不变 |
只要所有起点在开始扩展前都入队,队列仍按距离从小到大处理。若只让第一个源点跑完,再把第二个加进去,原先的距离已经占据许多格子,就不能再使用“访问过便跳过”的规则。
下面将同一过程用于 的四方向网格。 中 # 表示障碍,其他字符可走;、 保存至多 个合法源点坐标。所有数组全局声明,读完网格和源点后调用 。重复给出同一个源点也只加入一次;没有源点时,所有距离保持 。
int n,m,tot,sx[10005],sy[10005],dis[105][105];
char g[105][105];
int dx[4]={-1,1,0,0},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});
}
}
}
距离 的格子表示它至少可以由某个源点用 步到达。假如还有更早到达的方法,其前驱应该在更早的层被处理,目标也就早已被发现。因此第一次记录的是到最近源点的距离。每格仍只入队一次,总时间和空间都是 ;等代价前提与单源 BFS 相同。
8.2 路径记录:在首次发现时保存前驱
距离只回答走多少步,不能直接给出经过哪些格子。第一次从 发现 时,除了设置距离,还可以记住“ 是由 来的”。把这个前一个格子称为前驱。
例如空的 四方向网格,从 到 ,按上、下、左、右顺序扩展,会记录如下的一条前驱链:
| 格子 | 距离 | 首次发现它的前驱 |
|---|---|---|
| 起点,无前驱 | ||
先从终点倒着走,得到 ;逆序后才是从起点到终点的路线。每次回退距离都减一,最后一定走到距离为零的起点。其他最短路线也可能存在,但本题只要求一条,保留首次发现的前驱已经足够。
下面给出独立的四方向最短路径核心。范围为 ,网格 中 # 是障碍,起点 和终点 均可走。调用 后调用 ;不可达输出 -1,否则先输出步数,再逐行输出从起点到终点的坐标。、 分别保存前驱的行和列,、 暂存倒序路线。
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},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){puts("-1");return;}
int x=fx,y=fy,len=0;
while(1){
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]);
}
前驱与距离在同一次发现中写入,因此前驱边一定对应距离加一的那次移动。不能到终点以后再随便找一个“访问过”的邻居当作前驱,它的距离可能更大。起点等于终点时,先存入起点,再立即结束回退,得到步数为 、只有一个格子的路径;无需读取起点的前驱。BFS 耗时 ,恢复路线最多经过 个格子,数组和队列均占 空间。
8.3 从外部搜索:识别被包围的区域
设网格中 1 为墙,0 为空白,只能通过上下左右相邻的空白移动。要求把无法连到网格外部的空白改为 2。从某个内部空白开始搜索,也可以判断这一块是否碰到边界;但还需暂存整块并等待判断结果。换个方向,只找出“外部能够走到哪些空白”,剩余空白就能直接分类。
下面的 网格用墙围住一片空白,其中又放了一格墙。右下角另有一个与外部连通的空白:
11111
10001
10101
10001
11110
被围住的是中心墙周围的八个空白;中心的 1 仍然是墙。右下角的 0 虽然在图中离它们很近,却被墙隔开,只有右下角自身与外部连通。先按四方向连通逐格判断,就不会把“看起来靠近”误当成相连。
图中原网格由粗框圈出,额外的第 行、第 行、第 列、第 列都为空白。蓝色是从外圈可达的空白,橙色是原网格中尚未访问的空白,灰色是墙。额外外圈本身连成一圈,从 一点出发即可接触原网格的所有边界入口;不用为四条边分别启动搜索。
下面代码适用于 。原网格存入 ,全局数组其他位置初始为零,恰好形成空白外圈。 初始为假,读入后调用 ,再输出原范围内的 。若处理多组网格,需在每次读入前清空整个 和 ,不能留下上次的外圈或标记。
int n,m,a[105][105];
bool vis[105][105];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
void fill(){
queue<pair<int,int>> q;
vis[0][0]=1;
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]=1;
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。数组须能访问到第 行和第 列,时间和空间都是 。
9. 怎样选择搜索方式
| 目标 | 常用过程 | 访问状态的含义 |
|---|---|---|
| 列出或统计完整方案 | DFS 与回溯 | 当前选择前缀,需要按分支恢复 |
| 统计不重复经过格子的路径 | DFS 与回溯 | 当前路径经过的格子,返回时恢复 |
| 求等代价移动的最少步数 | BFS | 已确定的最短距离,首次发现后保留 |
| 求连通块数量 | DFS 或 BFS | 已处理的区域,整次扫描中保留 |
“判断能否到达”通常两种遍历都可以完成。选择前,应先写清状态包含哪些信息、一步可以转移到哪里、何时结束,以及两个表面相同的状态是否拥有相同的后续选择。DFS 的递归深度可能达到状态数,BFS 的队列也可能同时保存大量状态,都要按题目范围估算空间。
10. 作业
巩固练习
提高训练
- USACO 1.5·八皇后:列、对角线约束与全部方案计数。
- 填涂颜色:从外部识别封闭区域。
- 血色先锋队:多源 BFS 与最早到达时间。
练习时,先用一句话写出标记数组所表示的事实,再决定它应该在何时设置、何时恢复。这个判断比记住某个 DFS 或 BFS 模板更重要。
留言
可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。
正在加载留言区…