专题15 · 搜索2
上一讲我们学会了 DFS「一条路走到黑」。这一讲解决两个更实际的问题：
怎么让它别走冤枉路（剪枝），以及怎么保证第一次找到的就是最优解（BFS）。
三道题：八皇后、抓住那头牛、小猫爬山。
从"能搜出来"到"搜得快、搜得对"
上节回顾：DFS 的三个动作
① 从当前状态出发试每一种可能；
② 走到走不动为止（一条路走到黑）；
③ 退回来换一条路（回溯）。
代价：搜索树规模随层数指数级膨胀。
本节两块内容
块一 · 剪枝：在搜索树上"提前砍掉不可能的分支"，让指数变小。
块二 · BFS：改用队列一层一层扩散，天生保证"第一次到就是最短"。
① 八皇后
典型 DFS + 冲突判断，答案 92。
② 抓住那头牛
典型 BFS 最短路，首个解即最优。
③ 小猫爬山
剪枝策略的综合应用。
剪枝：在搜索树上"提前说不"
先看数字有多可怕：一层 3 个分支、深 15 层，就是 3¹⁵ ≈ 1400 万个节点； 深 20 层是 35 亿。剪枝不是"优化一点点"，是决定能不能在 1 秒内跑完。
① 优化搜索顺序
先搜分支少的节点（如小猫爬山按重量从大到小放）。 越早找到一个好的可行解，后面的最优性剪枝越有效。
② 排除等效冗余
几种选择本质一样时只搜一种。例：小猫爬山里"放进 1 号车"和"放进 2 号车"， 若两车剩余载重相同，是等效的 → 只试一个。
③ 可行性剪枝
往下走之前先检查这个状态合不合法：迷宫越界、重量超限、坐标出界…… 不合法就立刻返回，不再继续递归。
④ 最优性剪枝
已知一个可行解代价为 best，若当前累计代价已经 ≥ best， 再往下只会更差 → 整棵子树砍掉。这是最立竿见影的一条。
⑤ 记忆化
把算过的状态存下来，下次直接查表（上一讲已讲）。注意：它只适用于 状态可重复出现且结果与路径无关的题，八皇后、小猫爬山这类"路径相关"的题不适用。
同一棵树：剪枝到底省了多少
节点里的数字是代价，路径代价 = 从根到叶子的累加。目标是找最小。 已知当前最优解时，若累计代价已经 ≥ 最优，这棵子树就不必再看。
一层一层扩散，所以第一次到就是最短
为什么队列能保证最短
队列是先进先出：先处理距离 0 的所有点 → 再处理距离 1 的 → 再距离 2 的……
也就是说所有节点按"距离"从小到大出队。
因此某个节点第一次被访问时，走的肯定是最短路。
与 DFS 的结构差异
DFS 用栈（递归），是一条路走到底再回头；
BFS 用队列，是所有路齐头并进。
DFS 找"有没有"，BFS 找"最少几步"。
BFS 四步框架（背下来）
① 初始状态入队，并标记已访问（入队时就要标记，不是出队时） ② 队列非空时，取出队首 x ③ 若 x 是目标 → 答案就是 dist[x]，直接结束 ④ 枚举 x 能到达的每个 y：没越界 且 没访问过 → 标记、dist[y]=dist[x]+1、入队
盯着队列看：它怎么一层层长大
抓牛的 BFS：每一行都有理由
#include <iostream> #include <queue> using namespace std; const int MAXP = 200000; int dist[200005]; // ① dist 兼当 visited：-1 = 没走过 int main(){ int n, k; cin >> n >> k; for (int i = 0; i <= MAXP; i++) dist[i] = -1; // ② 初始化别漏 queue<int> q; dist[n] = 0; q.push(n); // ③ 起点：入队 + 标记（同时做！） while (!q.empty()){ int x = q.front(); q.pop(); if (x == k){ cout << dist[x] << '\n'; return 0; } // ④ 首次到达即最短 int nx[3] = { x - 1, x + 1, x * 2 }; for (int i = 0; i < 3; i++){ int y = nx[i]; if (y < 0 || y > MAXP) continue; // ⑤ 可行性剪枝（越界） if (dist[y] != -1) continue; // ⑥ 判重：走过的不回头 dist[y] = dist[x] + 1; // ⑦ 入队即标记 q.push(y); } } return 0; }
为什么上界是 200000
K ≤ 100000，走到 200000 以上必然绕远， 不可能比"先走到 K 附近"更优。
为什么能直接 return
BFS 按层扩散，第一次弹出 K 时 dist 已经是最小值。后面再有也只是更长的路。
数组开多大
MAXP = 200000，数组开 200005。
宁可稍大，不要刚好——x*2 很容易撞边界。
八皇后：把"不能互相攻击"翻译成三个数组
第一步：降维（最关键）
N 个皇后放 N 行 → 每行恰好一个。
于是不用"在 N² 个格子里选 N 个"，只需按行递归，每行决定放在哪一列。
搜索规模从 C(64,8) 降到 8⁸ 量级，再靠冲突判断砍掉绝大多数。
第二步：冲突怎么判
不同行（天然满足）；
同列 → col[c]；
主对角线（↘） → 同一条线上 行 − 列 恒定；
副对角线（↙） → 同一条线上 行 + 列 恒定。
③ 一个必踩的下标坑
行 − 列 会出负数（如第 1 行第 8 列 → −7），直接当数组下标就越界。
统一加一个偏移量：d1[row - c + n]，副对角线 d2[row + c] 最大 2n，数组开 2n+5。
int a = row - c + n; // 主对角线：偏移 +n 防负数 int b = row + c; // 副对角线：范围 2 ~ 2n if (col[c] || d1[a] || d2[b]) continue; // 任一被占 → 换一列
col[c] = d1[a] = d2[b] = 0;
忘了恢复，后面的行会误判成"冲突"，解数会变少（常见错误答案：0 或 1）。看它怎么试错、怎么回头
col/d1/d2 各点亮一位；回溯时三个同时熄灭——漏灭一个就全盘皆错。完整实现 + 为什么是 92
int n, col[20], d1[40], d2[40];
int total = 0, printed = 0;
vector<int> path;
void dfs(int row){
if (row > n){ // ① 最后一行也放好了 → 一个解
total++;
if (printed < 3){ // 只打印前 3 个解
for (int i = 0; i < n; i++){ if (i) cout << ' '; cout << path[i]; }
cout << '\n'; printed++;
}
return;
}
for (int c = 1; c <= n; c++){ // ② 枚举列
int a = row - c + n, b = row + c;
if (col[c] || d1[a] || d2[b]) continue; // ③ 冲突 → 试下一列
col[c] = d1[a] = d2[b] = 1; // ④ 现场标记
path.push_back(c);
dfs(row + 1);
path.pop_back();
col[c] = d1[a] = d2[b] = 0; // ⑤ ★ 回溯恢复，漏了就 WA
}
}
N=8 → 92
这是全解计数，不是"找到一个就停"。 所以不能在找到一个解后 return。
要不要剪枝
八皇后本身就是靠冲突判断做可行性剪枝。 想要更快可以上位运算优化（用 int 的位表示占用情况）。
常见 WA
① 忘了回溯；② 对角线下标没 +n 偏移； ③ 数组开小（d2 要 2n）；④ 找到一个解就 return。
把"移动方式"翻译成"图的边"
建模
状态 = 农夫所在的坐标 x（一个整数）；
边 = 三种移动：x−1、x+1、x×2，每条边长都是 1；
起点 = N，终点 = K；
求 = 最短路长度。
这就是标准的无权图最短路 → 直接 BFS。
样例 5 → 17
5 → 10（×2）→ 9（−1）→ 18（×2）→ 17（−1），共 4 步。
注意它先冲过头再往回退：×2 增长很快，往回退一点反而更短。
这也说明贪心（一直往 K 靠近）是错的，必须 BFS。
看距离是怎么一圈圈铺开的
剪枝策略的综合应用
N 只小猫要坐缆车下山，每辆缆车最大载重 W，求最少需要几辆。 三种剪枝同时上场：按重量从大到小放（优化顺序）、放不下就换车（可行性）、 车数已经 ≥ 已知最优（最优性）。
为什么从大到小
重猫选择少、更难安排，先处理难的能更早暴露矛盾、 更快剪枝；反过来先放轻猫，最后重猫无处可去，要试到很深才发现。
最优性剪枝
当前已用 c 辆车，已知最优 ans。
若 c >= ans，再怎么放也不会更好 → 整枝砍掉。
等效冗余
多辆车剩余载重相同时，放进哪辆都一样 → 只试一辆， 避免重复搜索等价方案。
同一张图，两种走法
DFS 适用
方案数、全排列、可达性、连通块、所有解。 用递归，注意回溯恢复现场和栈深度。
BFS 适用
最短步数、最快、最近、最少次数。 用队列，注意入队即判重和状态上界。
四个高频失分点
① 判重时机
❌ 出队时判重 → 同一个点被多个前驱重复入队，队列爆炸。
✅ 入队那一刻就标记 dist[y]=dist[x]+1。
② 回溯漏恢复
❌ 八皇后只标记不清零 → 解数变少甚至为 0。
✅ 标记与恢复成对出现，写了 =1 就找对应的 =0。
③ 对角线下标负数
❌ d1[row-c] 直接越界（或未定义行为）。
✅ 统一偏移：row-c+n；数组开到 2n+5。
④ 剪枝剪错了
❌ 最优性剪枝写成 cum > best 却在找到解前 best 没初始化 → 剪光。
✅ best 初始为无穷大；且只在确认代价单调不减时才敢这么剪。
知识树
搜索2 ─┬─ 剪枝（优化顺序 / 等效冗余 / 可行性 / 最优性 / 记忆化）
└─ BFS（队列 / 入队即判重 / 首次到达即最优 / 适用"最少"类问题）
一道题 100 分是分档给的——不会正解也要先拿保底
复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。
① 特判档：先别想算法，看数据范围表
题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行，
就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。
② 暴力档：按题意最直白地写一遍
多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。
③ 特殊性质档：题目里那句「若……」
常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。
④ 正解档：思路定了，就赢了八成
考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。
本讲 2 道题，各自的四档怎么走
八皇后 · QUEEN
第1档 · 2 分钟n == 1 → 1
第2档 · 8 分钟
枚举所有排列再判对角线，n ≤ 8 稳过
第3档 · 10 分钟
只做「不同行不同列」（不判对角线），先拿部分分
第4档 · 15 分钟
逐行 DFS + 列 / 主对角线 / 副对角线三个标记数组
抓住那头牛 · COW
第1档 · 2 分钟N ≥ K → 只能往回走，答案 = N − K
第2档 · 8 分钟
DFS 枚举所有路径取最短，深度 ≤ 15 稳过
第3档 · 10 分钟
只做 ±1（不做 ×2），先拿部分分
第4档 · 15 分钟
BFS 三方向扩展 + vis 数组，上界 0..100000
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查
freopen 与文件名。