搜索与剪枝

一、颠覆认知：搜索的“状态”，绝不仅仅是“当前坐标”

很多刚学完基础 DFS 和 BFS 的同学，脑海里对搜索的理解往往被固化为一句话：“不就是在网格图里走迷宫吗？x 和 y 不就是全部状态吗？”

到了提高组（CSP-S）考场，这种浅层认知会立刻暴露出致命问题。

1. 经典痛点：为什么同一个格子有时可以再来？

假设你在走迷宫。普通的迷宫求最短路，你从上方绕到格子 (x, y)，我从左侧绕到格子 (x, y)。如果接下来能走的路、面临的规则完全一样，那我们俩面对的就是完全等价的局面。此时谁先到保留谁，后到的直接作废，毫无争议。

但如果迷宫里加了一扇上锁的铁门，地图某处放着一把钥匙呢？

你两手空空走到了 (x, y)，我先绕去拿了钥匙，随后也走到了 (x, y)。我们两个人虽然此刻物理坐标完全重合，但接下来的命运天差地别：你能走的路我全能走，而铁门后面的宝藏只有我能去拿。

如果我们只用 vis[x][y] 来记录访问状态，你的标记就会把拿着钥匙的我挡在门外，程序当场漏掉正确答案！

在这个场景下，只存坐标是残缺的，完整的状态必须升维为三元组：

其中 $k \in \{0, 1\}$ 表示“手里是否持有钥匙”。访问数组也必须从 vis[x][y] 扩充为 vis[x][y][k]。

再比如：题目允许你在整场比赛中“穿墙一次”。此时的状态就是 $(x, y, t)$，$t$ 表示穿墙机会是否已经消耗。绝对不能因为“已经把穿墙机会用掉的我曾经来过这里”，就把“还保留着宝贵穿墙机会的我”当成重复访问给一脚踢开。

2. 状态完整性的判定铁律

在动手写任何搜索之前，先用这句灵魂拷问检验你的状态设计：

核心铁律：仅凭你当前状态变量里记录的这组数据，能否独立、无歧义地决定后续的所有合法选择？

如果不能，如果做决定时还需要“回头翻看之前的移动历史”，那就说明你的状态定义漏掉了关键信息！把那些真正会影响未来决策的历史轨迹提炼成变量，塞进状态维度里。无关紧要的散碎细节坚决丢弃，影响未来分支的条件半点不漏。

二、DFS 回溯的物理本质：借走的东西，回来一定要还

DFS（深度优先搜索）在微观上的执行动作，本质上是在一棵庞大的决策树上不断试探。

1. 借还法则与共享现场

以全排列为例：从数字 $1, 2, 3$ 中各取一次组成三位数。

第一位我们选择了 $1$，此时必须在全局数组中登记 vis[1] = 1。这个动作在物理层面上相当于：当前分支把数字 $1$ 的使用权“借走”了。

顺着这条路走到尽头，得到了方案 1 2 3。现在递归返回，我们要回到第二位去尝试选 $3$（组成 1 3 2）。如果返回时没有把刚才借走的数字 $3$ 和 $2$ 还回去，下一条分支一开门，就会以为 $3$ 已经被占用了，整个搜索树将全线崩塌。

这就是回溯的经典四步循环：

很多初学者容易患上“回溯强迫症”，恨不得在递归后把所有变量都还原一遍。请牢记：

• 必须撤销的：所有被多条分支共同读写的全局共享状态（如 vis[]、棋盘标记表、当前路径容器等）。
• 坚决不能撤销的：
  1. 全局答案收集器（如 ans++、best_val = min(...)），它们是各条分支努力探索的战果，撤销了就前功尽弃。
  2. 局部变量与按值传递的形参（如 dfs(u + 1) 中的 u + 1），函数弹栈时系统自动回收，根本不需要也不应该手动去减。

2. 排列与组合的根本分水岭：分支从哪里开始？

很多同学分不清排列与组合的代码区别。从 $n$ 个数里挑 $k$ 个数：

• 排列：有序。$(1, 3)$ 和 $(3, 1)$ 是两种不同方案。每次选下一个数时，依然要从头审视所有未借出的数。
• 组合：无序。$(1, 3)$ 和 $(3, 1)$ 是同一套方案。

消灭重复组合最优雅的手段，就是钦定单调性：规定选出来的数必须严格递增。上一位选了 $x$，下一位只能从 $x+1$ 开始往后挑。

看下面这段极其标准的组合搜索片段：

void dfs(int st) {
	// 终止条件：已凑齐 k 个数
	if ((int)cur.size() == k) {
		// 收集当前组合方案
		return;
	}
	int need = k - (int)cur.size(); // 当前还差几个数
	// 可行性剪枝：从 x 到 n 如果剩下的总数连 need 都凑不齐，直接勒马！
	for (int x = st; x <= n - need + 1; x++) {
		cur.push_back(x); // 做出选择
		dfs(x + 1);       // 强制下一位单调递增
		cur.pop_back();   // 回溯：撤销选择
	}
}

破题细节：为什么循环上界不是写死的 x <= n，而是 x <= n - need + 1？ 假设 $n=5, k=3$，当前我们手里只有 $1$ 个数，还差 $\text{need}=2$ 个数。如果我们此时去尝试枚举 $x=5$，后面根本没有任何数可选了，无论如何也凑不齐 $3$ 个数。 满足 $n - x + 1 \ge \text{need}$（剩余数字储备充足），移项后就是 $x \le n - need + 1$。这一行看似不起眼的边界控制，直接把大量注定夭折的分支扼杀在摇篮里。

三、经典回溯沙盘：有禁放格的 N 皇后问题

在 $n \times n$ 的国际象棋棋盘上摆放 $n$ 个皇后，使得任意两个皇后不能处于同一行、同一列或同一条对角线上。棋盘上某些格子标记为 #，禁止放置任何皇后（但注意：障碍物不阻挡皇后的视线攻击）。求合法的摆法总数。

1. 降维设计：为什么不用枚举格子的放与不放？

棋盘总共有 $n^2$ 个格子。如果我们在每个格子上都二选一（放/不放），状态树的规模是灾难性的 $2^{n^2}$。

物理观察：每一行至多放一个皇后，而总共必须放 $n$ 个皇后，且总共只有 $n$ 行。 这直接导出一个绝妙结论：每一行必须、且只能放恰好一个皇后！

我们直接让递归函数 dfs(r) 掌管第 $r$ 行的决策，在第 $r$ 行内从第 $1$ 列枚举到第 $n$ 列尝试安放。这样，“行冲突”在代码结构上被永久消灭了。

2. 灵魂对角线数组的数学映射

行冲突解决了，列冲突只需一个一维布尔数组 col[c] 即可登记。难点在于两条倾斜 $45^\circ$ 的对角线：

• 主对角线（左上到右下 $\searrow$）： 沿着这条线走，行号 $r$ 和列号 $c$ 同时增加 $1$。因此两者的差值是恒定不变的常数，即 $r - c = \text{const}$。 因为 $r - c$ 可能为负数（最小为 $1 - n$），为了能用作数组下标，我们全局偏移 $+n$，得到映射键值：

  $$\text{id}_1 = r - c + n$$

• 副对角线（右上到左下 $\swarrow$）： 沿着这条线走，行号 $r$ 增加 $1$，列号 $c$ 减少 $1$。因此两者的和是恒定不变的常数，即 $r + c = \text{const}$。映射键值直接就是：

  $$\text{id}_2 = r + c$$

准备在 $(r, c)$ 放皇后时，只要同时满足：

这三个数组不是什么神秘结构，就是三本极速查阅的占用登记表。

3. 四皇后单条成功路径手推实录

让我们在空的 $4 \times 4$ 棋盘上手推一条经典的合法路径（行列均从 $1$ 开始编号）：

1. 第 1 行：尝试第 $1$ 列（暂且略过其最终失败分支），我们看放第 $2$ 列的情况。在 $(1, 2)$ 摆放皇后，登记 col[2]=1, d1[1-2+4]=d1[3]=1, d2[1+2]=d2[3]=1。进入第 2 行。
2. 第 2 行：第 $1$ 列（副对角冲突）、第 $2$ 列（同列冲突）、第 $3$ 列（主对角冲突）全部碰壁！唯独第 $4$ 列完全合法。在 $(2, 4)$ 摆放，登记 col[4]=1, d1[2-4+4]=d1[2]=1, d2[2+4]=d2[6]=1。进入第 3 行。
3. 第 3 行：检查发现第 $1$ 列完全空闲！在 $(3, 1)$ 摆放，登记 col[1]=1, d1[3-1+4]=d1[6]=1, d2[3+1]=d2[4]=1。进入第 4 行。
4. 第 4 行：第 $1, 2, 4$ 列均已遭占用，仅剩第 $3$ 列安然无恙。在 $(4, 3)$ 摆放，登记 col[3]=1, d1[4-3+4]=d1[5]=1, d2[4+3]=d2[7]=1。

此时成功摆满 $4$ 行，输出这一组解的各行皇后的列号组合：2, 4, 1, 3！随后函数开始逐层回退，擦除登记标记，去探寻下一个可能的合法构型。

4. 完整程序一：统计有禁放格的 N 皇后合法摆法

输入格式：第一行一个整数 $n$（$1 \le n \le 13$）。接下来 $n$ 行，每行一个长度为 $n$ 的字符串，. 表示该格可以放置，# 表示该格禁止放置。 输出格式：一个整数，表示在棋盘上放置 $n$ 个互不攻击的皇后的合法方案总数。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=35;

int n,ans;
string a[N];
bool col[N],d1[N*2],d2[N*2];

void dfs(int r){
	// 成功放满 n 行，收获一个合法方案
	if(r>n){
		ans++;
		return;
	}
	
	for(int c=1;c<=n;c++){
		// 障碍物或已受同列、同对角线攻击
		if(a[r][c-1]=='#' || col[c] || d1[r-c+n] || d2[r+c]) continue;
		
		// 借走资源：登记占用
		col[c]=d1[r-c+n]=d2[r+c]=true;
		
		dfs(r+1); // 深入下一行
		
		// 归还资源：回溯撤销
		col[c]=d1[r-c+n]=d2[r+c]=false;
	}
}

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	ans=0;
	dfs(1);
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

• 时空复杂度解析： 若没有任何限制，每一行选一列的排列上限是 $n!$ 种可能；算法在每层作 $O(n)$ 的常数枚举与判断，宽松时间上界为 $O(n \cdot n!)$。在对角线剪枝与障碍物的强烈制约下，实际扩展的节点数远小于此上界。搜索深度固定为 $n$，空间复杂度为 $O(n^2)$（主存棋盘字符矩阵）。

四、剪枝的灵魂三问：剪掉的是废枝，不是希望

搜索最让人着迷的地方在于：一刀精准的剪枝，能让指数级的运行时间瞬间降维至毫秒级。

剪枝的核心原则就一条：必须在逻辑上严格证明被剪掉的整棵子树里绝对没有我们想要的答案。 盲目乱剪只会导致答案丢失（WA）。

竞赛中威力最大的三把剪枝神刀：

1. 深度剖析：最优性剪枝的“未来最乐观估计”

设当前已经花费代价 $cur$，全局已知最好答案是 $best$。如果我们能证明：从当前局面走到终点，至少还需要花费 $h$ 的代价。

那么只要满足：

我们就可以直接 return！因为最乐观的情况下总花费都无法超越（小于）$best$，继续在这个子树里深挖纯粹是浪费生命。

这里对 $h$ 的数学要求极其苛刻：$h$ 必须是一个不可逾越的理论下界（Admissible Lower Bound）。

• 如果实际至少需要花 $10$ 元，你保守估计 $h=6$，公式依然成立，剪枝虽然软了一点但绝对正确。
• 但如果你随口胡编一个 $h=12$，程序就会误以为这条路没救了，直接把真正的最优解剪得粉碎！

五、BFS 的波纹扩散：为什么“先到的一定是最短”？

如果说 DFS 是一只执拗的土拨鼠，不撞南墙不回头；那么 BFS（广度优先搜索）就是一滴滴入平静水面的墨水，一圈一圈、整齐划一地向外扩散。

1. 队列与距离单调性

在所有边权（移动代价）完全相等（通常为 1）的前提下：

• 起点距离为 $0$，入队。
• 从起点出发一步能到的所有点，距离为 $1$，全部入队。
• 从距离为 $1$ 的点出发一步能到的点，距离为 $2$，全部入队……

队列先进先出（FIFO）的物理特性，赋予了 BFS 一个无比神圣的性质：队列中所有节点对应的“距离”，天然具备单调不减性，且相邻节点的距离之差至多为 1。

这就从数学上保证了：任何一个格子第一次被搜索波纹触碰到的那一瞬间，记录下的距离必然就是全局最短距离！ 后续再有任何路径绕到该点，步数只可能更多或相等，绝不可能更少。

2. 灵魂细节：入队即打卡，切忌出队打卡！

初学者写 BFS 最容易犯的一个致命低级错误：

致命错误：从队列头部取出一个点时，才把它标记为 vis=true。

如果出队才标记，考虑四个相邻格子同时发现了同一个未访问点 $P$。因为 $P$ 还没出队，它的 vis 还是 $0$，这四个格子会同时把点 $P$ 重复压入队列 4 次！ 随着搜索深入，队列里的冗余垃圾会呈几何级数爆炸，直接把 $O(NM)$ 的高效图遍历拖垮成超时和爆内存的惨剧。

终极铁律：入队的一瞬间，必须立刻打卡（记录距离并标记访问）！ 只要拿到进站车票，就绝不允许任何人再给它发第二张票。

这里说的是边权全为 $1$ 的普通 BFS。边权为 $0/1$ 或一般非负数时，不能照搬“首次入队就定案”，要分别看《0-1 BFS》和《最短路》的松弛规则。

3. 为什么 BFS 通常不用回溯撤销标记？

很多同学学完 DFS 以后，写 BFS 时也总想着把 vis 改回 false。

• DFS 为什么要撤销？ 因为 DFS 的目标常常是穷举所有组合或路径形态，某个节点属于这条路径，退出来后还要参与另一条截然不同的路径竞争。
• BFS 为什么不撤销？ 因为在单位权值图中，BFS 的标记表示的是“到达该点的最短路已经被盖棺定论”。后来者即使绕出花来，步数也绝对不可能比第一次更优，根本没有二次探索的价值。

4. 完整程序二：四方向迷宫最短路

输入格式：第一行两个整数 $n, m$（$1 \le n, m \le 1000$）。接下来 $n$ 行，每行一个长度为 $m$ 的字符串，. 表示通道，# 表示墙壁。最后一行四个整数 $sx, sy, tx, ty$（$1$-based 坐标），分别表示起点的行列与终点的行列。 输出格式：一个整数，表示从起点到终点的最少移动步数。若无法到达或起点/终点本身就是墙壁，输出 -1；若起点与终点重合且均为通道，输出 0。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1005;

int n,m;
int sx,sy,tx,ty;
string a[N];
int d[N][N]; // 灵魂距离数组：兼具访问标记与距离记录双重功能

// 四方向位移向量
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};

void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>sx>>sy>>tx>>ty;
	
	// 起点或终点本身不可踏入
	if(a[sx][sy-1]=='#' || a[tx][ty-1]=='#'){
		cout<<-1<<'\n';
		return;
	}
	
	// 初始化距离数组为 -1（未访问状态）
	memset(d,-1,sizeof(d));
	
	queue<pair<int,int>> q;
	
	// 起点入队，立即打卡
	d[sx][sy]=0;
	q.push({sx,sy});
	
	while(!q.empty()){
		int x=q.front().first, y=q.front().second;
		q.pop();
		
		// 提前命中终点
		if(x==tx && y==ty) break;
		
		for(int k=0;k<4;k++){
			int nx=x+dx[k];
			int ny=y+dy[k];
			
			// 越界检查
			if(nx<1 || nx>n || ny<1 || ny>m) continue;
			// 障碍物或已被波纹访问过
			if(a[nx][ny-1]=='#' || d[nx][ny]!=-1) continue;
			
			// 入队即打卡！锁死最短路
			d[nx][ny]=d[x][y]+1;
			q.push({nx,ny});
		}
	}
	
	cout<<d[tx][ty]<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

• 时空复杂度解析： 在 $n \times m$ 的网格图中，每个格子至多入队一次、出队一次；每次出队仅遍历 $4$ 个相邻方向，故时间复杂度严格为 $O(n \cdot m)$。队列和距离矩阵占用的空间上限亦为 $O(n \cdot m)$，即使在 $1000 \times 1000$ 的数据规模下也能毫无压力瞬秒。

六、记忆化与回溯标记的本质抉择：借还现场还是永久封板？

许多同学在学完记忆化搜索（动态规划的递归写法）和普通 DFS 回溯后，经常被一段看似矛盾的代码折磨：

• 回溯搜索里：递归前 vis[u] = true;，递归一结束必须立刻 vis[u] = false;（借了必须还）。如果忘了清零，程序当场漏解！
• 记忆化搜索里：算完直接 memo[u] = ans; 封存，后续遍历无论如何也绝不能清零！如果每次返回都把 memo 还原，程序瞬间退化成指数爆炸，当场 TLE！

为什么同样是递归，一个必须“洗干净现场”，另一个却必须“焊死结果”？

1. 灵魂根源：路径依赖 vs 状态独立（无后效性）

区分两者的唯一标尺，是看当前结点的命运是否被到达它的具体路径所绑架：

• 回溯标记 vis[u] 的本质是“在栈标记”： 它的物理含义是：“结点 $u$ 当前正位于根结点到当前点的调用链（递归调用栈）上”。 我们之所以不能再踏入 $u$，是为了防止在图上转圈死循环。当我们退栈回到上一层时，$u$ 已经脱离了当前路径；如果从另一条完全不同的路径绕过来，$u$ 是完全合法且必须被允许踩上去的。因此，vis 必须随着退栈而解除。

• 记忆化标牌 memo[u] 的本质是“子问题独立答案”： 它的物理含义是：“从状态 $u$ 出发，能够到达目标的方案数 / 最优解，是一个客观恒定的数学常数”。 不管你是从左边走过来的，还是从右边绕过来的，只要踏进 $u$，后续面对的未来局面是完全一致的（即动态规划要求的无后效性）。既然答案与来路无关，第一次算出来的代价就可以直接永久生效，任何人后脚踩进来都能直接抄作业！

2. 菱形图手推沙盘：亲眼见证两种标记的命运分化

设有一张经典的有向无环菱形图：

• 起点为 $S$，终点为 $T$；
• 边集合为：$S \to A$，$S \to B$，$A \to B$，$A \to T$，$B \to T$。

场景一：求从 $S$ 到 $T$ 的所有简单路径（必须回溯）

从 $S$ 出发先探寻左支：走 $S \to A \to B \to T$。在深入过程中，$A$ 和 $B$ 被打上 vis 标记。这是一条合法路径。 返回 $A$ 后还会探索 $S \to A \to T$，再逐层退栈回到 $S$，准备探寻右支 $S \to B$：

• 如果执行了回溯撤销：$B$ 的 vis 已经被清零，$S \to B \to T$ 得以顺利检出，全解收集完毕！
• 如果不撤销回溯：由于探寻第一条路时 $B$ 已经盖戳，右路出发时发现 vis[B] == true 直接放弃，永远丢失了 $S \to B \to T$ 这一正解！

场景二：求从 $S$ 到 $T$ 的不同路径总数（必须记忆化）

设 $f(u)$ 表示从结点 $u$ 出发走到终点 $T$ 的路径数。 显然数学上有：从 $B$ 走到 $T$ 只有 $B \to T$ 这一条路，即无论何时 $f(B) = 1$。

• 当第一条支路深入到 $B$ 并算完后，全局登记 memo[B] = 1；
• 退回到 $S$，展开第二条支路 $S \to B$ 时，程序发现 $memo[B]$ 已经有值，直接读取返回 $1$；
• 如果这里脑抽写了回溯清空 memo[B] = 0：第二条支路就必须重新把 $B$ 后面的整棵子树重新遍历一遍。在大型 DAG 上，这种“忘掉成果”的行为会把 $O(V + E)$ 的线性记忆化打回 $O(2^V)$ 的指数地狱！

3. 实战检验速查表

七、进阶视野：双向搜索与迭代加深 (IDDFS)（选学）

掌握了经典的单向 DFS 与 BFS 之后，面对更加严苛的竞赛题，我们往往需要借用两种极其精妙的降维思路：

1. 双向广搜 (Bidirectional BFS)：相向而行的降维打击

假设一棵搜索树每个节点分叉出 $b$ 个分支，目标在深度为 $d$ 的层级。

• 普通 BFS 的搜索空间规模是 $b^d$。
• 如果我们同时从起点和终点各自开启一个 BFS 队列，两束波纹在中间相遇： 两端各自只用搜索 $\frac{d}{2}$ 的深度，总体积变为 $2 \times b^{d/2}$！

当 $b=4, d=20$ 时： $4^{20} \approx 10^{12}$（彻底 TLE）； 而 $2 \times 4^{10} \approx 2 \times 10^6$（轻松秒杀）！这就是指数级折半带来的巨大威力。

2. 迭代加深 (IDDFS)：用 DFS 的极低空间，换取 BFS 的最短路特权

• BFS 的痛点：空间随着层级扩张呈指数级爆炸，极其容易 MLE（内存超限）。
• DFS 的痛点：空间极小（只与递归深度成正比），但一旦扎进无底洞的无限深分支，可能永远找不到浅层的最优解。

IDDFS 的折中哲学： 我们手动限制 DFS 的最大递归深度上限 $limit$。

1. 先设 $limit = 0$，用 DFS 搜一遍；
2. 如果没找到答案，再设 $limit = 1$，重新跑一遍 DFS；
3. 逐步将 $limit$ 递增为 $2, 3, 4 \dots$。

看似浅层节点被重复搜索了多次，但由于搜索树的节点绝大多数都集中在底层（底层的节点数往往占据了整棵树总和的大半），重复搜索浅层带来的时间代价完全可以忽略，而我们却同时斩获了：

• DFS 的空间优势：空间复杂度只有极其轻量级的 $O(limit)$；
• BFS 的层级优势：首次成功找到的解，必然是最短步数解！

八、双向 BFS 的工程落地：按层交替、反向转移与相遇判断（选学）

在前面的“进阶视野”中，我们领略了双向广搜把指数爆炸折半的数学魅力（$2 \times b^{d/2} \ll b^d$）。但在考场上，很多同学写双向 BFS 会遭遇以下三大暗礁：

1. 盲目交替：前向走一步、后向走一步，结果某一边分支系数极大，队列单向打爆；
2. 反向转移写错：在有向图或非对称操作中，反向搜索没有逆向建图或没有使用逆操作；
3. 相遇结算过早或过晚：没有正确识别两军会师的边界条件。

1. 为什么不能闭着眼轮流走一步？按层规模贪心交替

如果搜索树两端的分支系数不对称（例如正向每个状态分叉 8 个，反向每个状态分叉 2 个），机械地“正向弹一个、反向弹一个”会导致正向队列急剧膨胀，完全丧失双向剪枝的优势。

工程级标准实现采用贪心策略：

核心准则：每一轮只选择当前队列元素更少的那一端，并一口气将其整整一层（整个距离层级）的所有结点全部扩展完毕！

通过每次挑“软柿子”（当前波纹周长较小的一侧）扩展一层，既保证了距离维度的单调推进，又能牢牢压制总状态数的膨胀速度。

2. 反向转移的致命陷阱：逆流而上的反向建图

无向图里，正走反走是对称的；但在有向图或状态变换题中，反向必须完全走“逆规则”：

• 图论搜索：正向沿着出边邻接表 $g[u]$ 走；反向必须沿着入边反向邻接表 $rg[u]$ 走！
• 代数/数字变换：正向操作若是 $x \leftarrow x \times 2$ 与 $x \leftarrow x + 1$，反向搜索在扩展时必须倒过来应用逆操作：若 $x$ 为偶数则分支 $x \leftarrow x / 2$，以及分支 $x \leftarrow x - 1$！如果反向依然做加法和乘法，两束光束背道而驰，永无相遇之日。

3. 相遇判定与层级结算

我们维护两个独立的距离记录表：d1[]（正向）和 d2[]（反向），初始化全为 -1。

• 正向起点 $s$：d1[s] = 0，入队 q1；
• 反向终点 $t$：d2[t] = 0，入队 q2；
• 当正向队列扩展边 $u \to v$ 时：
  • 如果发现 d2[v] != -1，说明反向搜索早已到达过 $v$！两军当场会师，全局最短距离即刻敲定为：
    $$\text{ans} = d1[u] + 1 + d2[v]$$
  • 若未被反向访问过，且 d1[v] == -1，则登记 d1[v] = d1[u] + 1，并将 $v$ 压入 q1。
• 反向扩展对称处理。

4. 完整程序三：有向图双向广搜极速最短路

输入格式：第一行四个整数 $n, m, s, t$（$1 \le n \le 10^5, 1 \le m \le 2 \times 10^5, 1 \le s, t \le n$），分别表示有向图的点数、边数、起点与终点。接下来 $m$ 行，每行两个整数 $u, v$，表示一条从 $u$ 到 $v$ 的有向边（边权为 $1$）。 输出格式：一个整数，表示从 $s$ 到 $t$ 的最少步数；若不可达输出 -1。

输入样例：

text复制代码

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

输出样例：

text复制代码

2

(样例解释：存在路径 1 -> 3 -> 5，只需 2 步即可到达)

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=100005;

int n,m,s,t;
vector<int> g[N], rg[N]; // g 为正向图，rg 为反向图
int d1[N], d2[N];        // d1 记录正向步数，d2 记录反向步数

int bi_bfs(){
	if(s == t) return 0;
	
	memset(d1, -1, sizeof(d1));
	memset(d2, -1, sizeof(d2));
	
	queue<int> q1, q2;
	d1[s] = 0; q1.push(s);
	d2[t] = 0; q2.push(t);
	
	while(!q1.empty() && !q2.empty()){
		// 贪心策略：优先扩展较小的队列整整一层
		if(q1.size() <= q2.size()){
			int sz = q1.size();
			while(sz--){
				int u = q1.front(); q1.pop();
				for(int v : g[u]){
					if(d2[v] != -1) return d1[u] + 1 + d2[v]; // 会师终点！
					if(d1[v] == -1){
						d1[v] = d1[u] + 1;
						q1.push(v);
					}
				}
			}
		} else {
			int sz = q2.size();
			while(sz--){
				int u = q2.front(); q2.pop();
				// 注意：反向搜索必须沿着入边反向追溯！
				for(int v : rg[u]){
					if(d1[v] != -1) return d2[u] + 1 + d1[v]; // 会师终点！
					if(d2[v] == -1){
						d2[v] = d2[u] + 1;
						q2.push(v);
					}
				}
			}
		}
	}
	return -1;
}

void solve(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		rg[v].push_back(u); // 同步构建反向图
	}
	cout<<bi_bfs()<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

九、IDA* 启发式迭代加深：乐观估价与可采纳剪枝（选学）

先修提示：阅读本节前，请确保已经理解了本讲第七节的 IDDFS（用限制深度把 DFS 模拟成 BFS）以及第四节的最优性剪枝下界思想。

普通的迭代加深（IDDFS）虽然解决了空间爆炸问题，但每次遇到广阔的分支时，依然如同“无头苍蝇”般盲目全搜。如果每一层分叉极大，DFS 仍然会耗费巨量时间在毫无希望的浅层死胡同里试错。

能不能在搜索时给 DFS 装上一副透视眼镜？这就是 IDA* (Iterative Deepening A*)。

1. 核心公式与物理含义

在搜索的任意一个状态结点 $u$，我们定义评估总代价的准则：

• $g(u)$：从初始状态走到当前状态已经耗费的实际真实步数；
• $h(u)$：从当前状态走到目标状态，至少还需要花费的理论估计步数（启发式估价，Heuristic）；
• $f(u)$：经过状态 $u$ 到达目标的最乐观预期总步数。

在限制最大深度为 $limit$ 的某一轮迭代中，一旦发现：

立刻打道回府（剪枝退出）！ 因为哪怕接下来的路顺风顺水、没有任何阻碍，走完的总代价也必然打破了本轮尝试的上限 $limit$。

2. 估价函数的及格线：为什么必须“绝对乐观”（可采纳性）？

和第四节第 1 小节一样，估价必须满足 $h(u) \le h^*(u)$（$h^*(u)$ 是真实剩余最少步数）：宁可低估、少剪一点，也不能高估而剪掉最优解，这就是可采纳性。

3. 经典沙盘：5×5 棋盘“骑士精神”的错位估价

在 $5 \times 5$ 的棋盘上有 12 匹白马、12 匹黑马和一个空格（用 * 标识）。题目要求通过马走日字规则（马与空格交换位置），在不超过 $15$ 步内将棋盘还原为特定的终态构型。

终态如下（1 代表白马，0 代表黑马）：

1 1 1 1 1
0 1 1 1 1
0 0 * 1 1
0 0 0 0 1
0 0 0 0 0

面对这个庞大的状态图，单向 BFS 空间当场爆掉，普通 DFS 搜到深度 15，要面对 $8^{15}$ 量级的状态，直接跑死。如何设计绝对乐观的 $h$ 函数？

物理观察与严格下界推导： 每次让空格移动一步（即一匹马跳入空格），在物理上最多只能把一匹原本位置错误的马，安置到它的正确目标格上。

因此： 设当前棋盘上，除去空格所在的格子外，与最终目标盘面颜色不同的格子总数为 $cnt$。 因为一步操作最多消灭 $1$ 个错位，要消灭全部 $cnt$ 个错位，至少需要移动 $cnt$ 步！

这个不等式在任何合法局面下都 $100\%$ 成立，可采纳性得证！只要当前已走步数 $g + cnt > limit$，这一分支必死无疑，直接截断。

4. 完整程序四：IDA* 求解骑士精神（15 步极限挑战）

输入格式：第一行一个整数 $T$（$1 \le T \le 10$），表示测试用例组数。接下来包含 $T$ 组输入，每组测试用例由 $5$ 行长度为 $5$ 的字符串组成，表示棋盘的初始局面，包含字符 0、1 与 *。 输出格式：对于每组测试数据，输出一行一个整数，表示最少移动步数。若在 $15$ 步以内（含 $15$ 步）无法达成目标，输出 -1。

输入样例：

text复制代码

1
1*111
01111
00111
00001
00000

输出样例：

text复制代码

1

(样例解释：只需将位于 (3, 3) 的 1 号白马跳入 (1, 2) 的空格中，一步即可达成标准目标态)

#include<bits/stdc++.h>
#define int long long
using namespace std;

string goal[5] = {
	"11111",
	"01111",
	"00*11",
	"00001",
	"00000"
};

string b[5];
bool ok;

// 国际象棋“马走日”的 8 个偏移向量
int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

// 乐观估价函数：计算与目标盘面不吻合的格子总数
int get_h(){
	int diff = 0;
	for(int i=0; i<5; i++){
		for(int j=0; j<5; j++){
			if(b[i][j] != '*' && b[i][j] != goal[i][j]) diff++;
		}
	}
	return diff;
}

void dfs(int g, int limit, int x, int y, int px, int py){
	if(ok) return;
	
	int h = get_h();
	if(h == 0){
		ok = true;
		return;
	}
	
	// IDA* 核心：理论极限已经冲破当前轮上限，果断勒马！
	if(g + h > limit) return;
	
	for(int k=0; k<8; k++){
		int nx = x + dx[k];
		int ny = y + dy[k];
		// 越界检查
		if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
		// 剪除立即掉头的无意义两步死循环（不能立刻踩回上一个空格位置）
		if(nx == px && ny == py) continue;
		
		swap(b[x][y], b[nx][ny]);
		dfs(g + 1, limit, nx, ny, x, y);
		swap(b[x][y], b[nx][ny]); // 回溯恢复现场
	}
}

void solve(){
	int sx = -1, sy = -1;
	for(int i=0; i<5; i++){
		cin>>b[i];
		for(int j=0; j<5; j++){
			if(b[i][j] == '*') sx = i, sy = j;
		}
	}
	
	// 迭代加深外层驱动：逐步放宽步数上限 limit
	for(int limit = 0; limit <= 15; limit++){
		ok = false;
		dfs(0, limit, sx, sy, -1, -1);
		if(ok){
			cout<<limit<<'\n';
			return;
		}
	}
	cout<<-1<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}

十、渐进式实战练习与破题自测

1. 课堂沙盘极速自测

在转战真题前，先在脑海中不看代码模拟下面两个极端测试用例，理解程序防御机制的物理意义：

1. 测试一：把程序一（N 皇后）的第一行所有格子全设为 #，输出为什么必然是 0？
   • 推导：第 $1$ 行枚举所有列时全部触发障碍物跳过，循环结束直接退栈，压根没有机会展开后续任何一行的递归。
2. 测试二：把程序二（迷宫）的起点与终点输入相同的可通行格子坐标（如 1 1 1 1），输出为什么必然是 0？
   • 推导：起点入队时 d[sx][sy] = 0，进入 while 循环第一次取出队首即命中 x == tx && y == ty 触发 break，直接输出当前已登记的 0。

2. 阶梯式题单

第一阶段：回溯标记与棋盘沙盘精修

1. 洛谷 P1219 [USACO1.5] 八皇后 Checker Challenge
   • 破题指引：本题不含障碍物，数据范围 $6 \le n \le 13$。要求按字典序输出前 $3$ 个解的列号序列，最后一行输出总方案数。解题时需额外开一个数组记录当前递归路径上的列号，遇到叶子节点时先判断是否需要打印前 $3$ 组解，再累加计数。

第二阶段：广度搜索波纹与步数扩散

2. 洛谷 P1443 马的遍历
   • 破题指引：把本篇迷宫的四方向位移向量，替换为象棋中“马走日”的 $8$ 个偏移行列差。本题要求输出整张棋盘上每一个格子从起点的最少跳跃步数，因此不能在遇到特定终点时 break，必须让队列波纹自然枯竭，将所有能够波及的联通区域完全填满，不可达的位置保留默认值 -1 格式化输出。