第十章:搜索与回溯

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

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

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

各节代码按 C++17 编写。第 1 至第 6 节给出独立的完整程序;第 7、8 节保留用于比较不同搜索方法的核心片段,并说明初始化与调用方式。每段代码使用自己的全局数组和函数,不能直接拼成同一个程序。网格除特别说明外按行、列从 11 开始编号,行向下增加,列向右增加。

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

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

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

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

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

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

回溯关键帧:输出 123 后依次撤销 3 和 2,再尝试 132

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

下面是完整程序,输入一行整数 nn,每行输出一个排列。数组下标从 11 开始;为使输出规模可控,本例取 1≤n≤91\le n\le9,a[25]a[25] 和 used[25]used[25] 均足够。读入 nn 后调用 dfs(1)\texttt{dfs(1)},全局 usedused 初始为假。若在同一进程处理多组数据,开始每组前重新清空标记。

#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;
}

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

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

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

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

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

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

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

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

第二位候选 xx比它大的数后面还需 11 个是否继续
223,4,53,4,5足够继续
334,54,5足够继续
4455刚好继续
55无不足不必进入下一层

令 dfs(u,last)\texttt{dfs(u,last)} 负责填写第 uu 个位置,lastlast 是上一位选中的整数。当前共需填写 r−u+1r-u+1 位;选好本位的 xx 后,剩下 r−ur-u 位,而比 xx 大的数共有 n−xn-x 个。要能填完,必须满足

n−x≥r−u,x≤n−(r−u).n-x\ge r-u,\qquad x\le n-(r-u).

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

#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;
}

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

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

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

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

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

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

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

皇后棋盘:两种对角线编号,以及前两行放在第 2、4 列后的第三行候选

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

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

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

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

#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;
}

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

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

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

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

先用没有障碍的 2×32\times3 网格,从左上角 SS 到右下角 TT。给其他格子临时起名,便于描述路线:

S A B
C D T

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

同一格 A 的两份路径状态:直接从 S 到 A 时 D 未用,绕经 C、D 到 A 时 D 已用

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

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

这里 used[x][y]used[x][y] 的确切含义是“格子 (x,y)(x,y) 已出现在当前递归路径上”。对需要继续扩展的格子,进入时标记,离开当前递归分支时撤销。终点是提前结算的情况:到达就返回一条路径,不继续扩展,也不设置标记。设障碍由 wallwall 标记,起点和终点都不是障碍,从起点调用 dfs(sx,sy)\texttt{dfs(sx,sy)}。完整程序沿用练习《迷宫》的输入格式:首行 n,m,tn,m,t,下一行 sx,sy,fx,fysx,sy,fx,fy,接着 tt 行障碍坐标,输出路径数:

#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;
}

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

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

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

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

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

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

刚出队的格子它的距离本次新发现操作后的队列(从队首到队尾)
尚未出队—起点 (1,1)(1,1)(1,1)(1,1)
(1,1)(1,1)00(2,3),(3,2)(2,3),(3,2)(2,3),(3,2)(2,3),(3,2)
(2,3)(2,3)11(3,1)(3,1)(3,2),(3,1)(3,2),(3,1)
(3,2)(3,2)11(1,3)(1,3)(3,1),(1,3)(3,1),(1,3)
(3,1)(3,1)22(1,2)(1,2)(1,3),(1,2)(1,3),(1,2)
(1,3)(1,3)22(2,1)(2,1)(1,2),(2,1)(1,2),(2,1)
(1,2)(1,2)33(3,3)(3,3)(2,1),(3,3)(2,1),(3,3)
(2,1)(2,1)33无;(3,3)(3,3) 已发现(3,3)(3,3)
(3,3)(3,3)44无空

骑士 BFS 的棋盘距离和关键队列:两个距离为 3 的前驱都能遇到右下角

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

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

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

#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;
}

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

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

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

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

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

11000
01010
00010
10000

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

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

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

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

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

#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;
}

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

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

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

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

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

本节代码采用从 00 开始的下标,先把数字降序排列为 a0≥a1≥⋯≥an−1a_0\ge a_1\ge\cdots\ge a_{n-1},从左到右选择下标递增的 kk 个数。令 dfs(start,chosen,sum)\texttt{dfs(start,chosen,sum)}:下一次只能从 startstart 及之后的下标选择;chosenchosen 个数已经选定,当前总和为 sumsum。例如 [8,6,6,3,1][8,6,6,3,1]、k=2k=2、L=11L=11,先尝试 88,再试 66 得到 1414,超过上限;改试 33 得到 1111,已经找到可行答案。

先不考虑额外的剪枝,按递增下标选出恰好 kk 个数,到叶子再检查是否超限。下面是独立的基准核心:aa 已按降序排列,ans=−1ans=-1,调用 dfs(0,0,0)\texttt{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]);
}

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

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

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

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

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

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

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

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

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

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

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

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

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

剪枝搜索树:8 加 6 超限,3 与 1 的分支上界为 4,同层第二个 6 被合并

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

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

下面给出加入这些判断后的搜索核心。a[0],…,a[n−1]a[0],\ldots,a[n-1] 已按降序排列,代码中的 limitlimit 保存题目上限 LL,ansans 初始为 −1-1,表示尚无可行方案;调用 dfs(0,0,0)\texttt{dfs(0,0,0)}。搜索结束后,若 ans=−1ans=-1,表示不存在满足条件的组合。所有数字及总和若可能超过 int\texttt{int} 的范围,应把数组元素、LL、ansans 与 sumsum 一起改为 long long\texttt{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=kchosen=k 时,当前和就是一个完整方案;非负性保证超限判断安全。upperupper 是当前分支中任意补全方案的上界,upper≤ansupper\le ans 时不会错过更大答案。同层去重只删除数值相同的下一选择,留下的分支仍覆盖每一种不同的数值组合。没有任何剪枝时,枚举至多涉及 O(2n)O(2^n) 个子集结点;代码每个结点至多扫描 O(n)O(n) 个候选和上界元素,因此保守时间上界为 O(n2n)O(n2^n),递归深度为 O(k)O(k)。剪枝改善实际运行量,但不保证改变最坏情况上界。

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

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

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

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

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

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

操作队列(队首在左)已知距离,- 表示未发现
两端一起入队1,51,50,−,−,−,00,-,-,-,0
取出 11,发现 225,25,20,1,−,−,00,1,-,-,0
取出 55,发现 442,42,40,1,−,1,00,1,-,1,0
取出 22,发现 334,34,30,1,2,1,00,1,2,1,0
取出 44,遇到已发现的 3333不变

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

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

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});
        }
    }
}

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

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

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

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

格子距离首次发现它的前驱
(1,1)(1,1)00起点,无前驱
(2,1)(2,1)11(1,1)(1,1)
(2,2)(2,2)22(2,1)(2,1)
(2,3)(2,3)33(2,2)(2,2)

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

下面给出独立的四方向最短路径核心。范围为 1≤n,m≤1001\le n,m\le100,网格 gg 中 # 是障碍,起点 (sx,sy)\texttt{(sx,sy)} 和终点 (fx,fy)\texttt{(fx,fy)} 均可走。调用 bfs()\texttt{bfs()} 后调用 print_path()\texttt{print\_path()};不可达输出 -1,否则先输出步数,再逐行输出从起点到终点的坐标。pxpx、pypy 分别保存前驱的行和列,aa、bb 暂存倒序路线。

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]);
}

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

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

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

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

11111
10001
10101
10001
11110

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

给网格加空白外圈,从外圈搜索;墙、外部可达空白、内部封闭空白分开显示

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

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

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。数组须能访问到第 n+1n+1 行和第 m+1m+1 列,时间和空间都是 O(nm)O(nm)。

9. 怎样选择搜索方式

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

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

10. 作业

巩固练习

提高训练

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

留言

可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。