本次两个模块：
| 模块 | 内容 | 复用的旧讲义 | 本讲义新写 |
|---|---|---|---|
| M9 递归、DFS、组合 | 递归三要素、DFS 框架（排列/组合/网格）、回溯、剪枝、组合数、杨辉三角 | L06 全部 |
剪枝、加法/乘法原理、组合数递推（杨辉三角） |
| M10 BFS、连通块、图 | BFS 框架、多源 BFS、Flood Fill、图的存储与遍历 | L07 全部、S6 第二节 |
连通块计数、图上的 DFS/BFS |
输入 n（1 ≤ n ≤ 8），按字典序输出 1~n 的全排列，每行一个，数之间用一个空格隔开。
输入
3→ 输出 6 行：1 2 3/1 3 2/2 1 3/2 3 1/3 1 2/3 2 1
#include <bits/stdc++.h>
using namespace std;
int n, path[10];
bool used[10];
void dfs(int k) { // 正在填第 k 个位置
if (k > n) { // 边界：n 个位置都填满了
for (int i = 1; i <= n; i++) cout << path[i] << (i == n ? '\n' : ' ');
return;
}
for (int x = 1; x <= n; x++) {
if (used[x]) continue;
used[x] = true; path[k] = x; // 做选择
dfs(k + 1); // 往下走
used[x] = false; // 撤销选择（回溯）
}
}
int main() {
cin >> n;
dfs(1);
return 0;
}写对了 → 直接看 1.2 起。写不出 →
先读 L06 的"DFS 四行框架"和"排列型"。
| 内容 | 在哪 |
|---|---|
| 递归三要素、DFS 四行框架 | L06 前半 |
排列型（全排列）、组合型（选数 P1036，别忘了
start）、网格型（迷宫） |
L06 后半 |
| 忘记回溯时官方样例照样能过、要自造数据才暴露 | L06 迷宫一节 |
DFS 会试遍所有可能，剪枝就是"这条路一看就不可能了，别再往下走"。两种最常用：
| 剪枝 | 意思 | 例子 |
|---|---|---|
| 可行性剪枝 | 再往下走一定不满足条件 | 要选若干个数凑出和 S，当前和已经超过 S（数都是正的） |
| 最优性剪枝 | 再往下走一定不会比已知答案更好 | 求最少步数，当前步数已经 ≥ 已知最优答案 |
例：从 n 个正整数里选若干个，和恰好为 S，有几种选法？
#include <bits/stdc++.h>
using namespace std;
int n, S, a[25], ans = 0;
void dfs(int start, int sum) {
if (sum == S) { ans++; return; } // 凑够了（数都是正的，再选只会更大）
for (int i = start; i <= n; i++) {
if (sum + a[i] > S) break; // 可行性剪枝：a 已排序，后面的更大，全都不行
dfs(i + 1, sum + a[i]);
}
}
int main() {
cin >> n >> S;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1); // 排序后才能用 break 剪掉后面所有
dfs(1, 0);
cout << ans << endl;
return 0;
}⚠️ break
能剪掉"后面所有"，前提是数组排过序。 没排序就只能
continue（只跳过这一个），效果差很多。
⚠️ 剪枝不能剪错。 如果题目里有负数，"当前和超过 S"就不代表以后一定超，这个剪枝就是错的。写剪枝前先问：这个"一定"真的一定吗？
| 原理 | 什么时候用 | 例子 |
|---|---|---|
| 加法原理 | 完成一件事有几类办法，每类里任选一种 | 从 A 到 B 有 3 条公路或 2 条铁路：3 + 2 = 5 种 |
| 乘法原理 | 完成一件事要分几步，每步都要做 | 从 A 到 B 有 3 条路，B 到 C 有 2 条路：3 × 2 = 6 种 |
排列数：从 n 个里选 k 个排成一列，A(n,k) = n × (n−1) × … × (n−k+1)（乘法原理：第一个位置 n 种，第二个 n−1 种……）。
组合数：从 n 个里选 k 个不管顺序，C(n,k) = A(n,k) / k!。
直接用阶乘算 C(n,k)，n 稍大就溢出。编程时用递推：
C(n,k) = C(n−1,k−1) + C(n−1,k)
意思是：看第 n 个元素选不选。选它，剩下 n−1 个里再选 k−1 个；不选它，剩下 n−1 个里选 k 个。（加法原理）
把 C(n,k) 排成三角形，就是杨辉三角：每个数等于它肩上两个数之和。
#include <bits/stdc++.h>
using namespace std;
long long C[70][70];
int main() {
int n = 60;
for (int i = 0; i <= n; i++) {
C[i][0] = 1; // 边界：一个都不选，1 种
for (int j = 1; j <= i; j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
for (int i = 0; i <= 4; i++) { // 打印杨辉三角前 5 行
for (int j = 0; j <= i; j++) cout << C[i][j] << (j == i ? '\n' : ' ');
}
cout << C[5][2] << " " << C[60][30] << endl;
return 0;
}⚠️ n 超过约 66 时 long long
也装不下，题目通常会让你对某个数取模：每一步加完就
% p。A 档作业 P2822 组合数问题就是"杨辉三角取模 +
K04 的二维前缀和"。
输入 n、m 和一个 n×m 的网格（
0可走、1是墙），从左上角走到右下角，每步上下左右走一格，输出最少步数，走不到输出-1。n、m ≤ 1000。输入：
3 4 0 0 1 0 0 0 0 0 0 1 0 0输出：
5
#include <bits/stdc++.h>
using namespace std;
int n, m, g[1005][1005], dist[1005][1005];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cin >> g[i][j];
memset(dist, -1, sizeof(dist)); // -1 表示没到过，兼当 vis
queue<pair<int, int>> q;
if (g[0][0] == 0) { q.push({0, 0}); dist[0][0] = 0; }
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (g[nx][ny] == 1 || dist[nx][ny] != -1) continue;
dist[nx][ny] = dist[x][y] + 1; // 入队即标记
q.push({nx, ny});
}
}
cout << dist[n - 1][m - 1] << endl;
return 0;
}⚠️ 网上常见的 auto [x, y] = q.front();
别学。 这是 C++17 的写法：你们的 Dev-C++ 5.11
直接编译不过；评测机用 C++14
编译时只报警告，但不保证。老老实实写
.first、.second。
| 内容 | 在哪 |
|---|---|
queue 五件套、BFS 框架、dist 填 -1 兼当
vis、入队即标记 |
L07 |
| 奇怪的电梯（一维 BFS）、马的遍历（八个方向）、多源 BFS（草原起火） | L07 |
邻接表 vector<int> g[N] |
S6 第二节 |
"有几个水塘""有几个细胞""有几块陆地"——都是连通块计数：
#include <bits/stdc++.h>
using namespace std;
int n, m;
char g[105][105];
bool vis[105][105];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
void dfs(int x, int y) { // 把 (x,y) 所在的整块标记掉
vis[x][y] = true;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (g[nx][ny] != '#' || vis[nx][ny]) continue;
dfs(nx, ny); // 这里不用回溯：标记过就永远不再进
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> g[i];
int cnt = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == '#' && !vis[i][j]) { cnt++; dfs(i, j); }
cout << cnt << endl;
return 0;
}⚠️ 三个坑：
L06
迷宫"走完要回溯"不一样。连通块问的是"能不能到"，迷宫问的是"有几条路"。网格是一种特殊的图：每个格子是一个点，相邻格子之间有边。一般的图用邻接表存（S6），DFS/BFS
的框架一个字不改，只是"下一步去哪"从"四个方向"换成"g[u]
里的每一个邻居"。
下面的程序读入一张无向图，用 BFS 求点 1 到每个点最少经过几条边：
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
int dist[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u); // 无向图：两边都要加
}
memset(dist, -1, sizeof(dist));
queue<int> q;
q.push(1); dist[1] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) { // 和网格 BFS 唯一的区别在这一行
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q.push(v);
}
}
for (int i = 1; i <= n; i++) cout << dist[i] << (i == n ? '\n' : ' ');
return 0;
}📝 邻接矩阵 vs 邻接表：
邻接矩阵 g[u][v] |
邻接表 vector<int> g[u] |
|
|---|---|---|
| 内存 | n² | n + m |
| n = 10⁵ 时 | 10¹⁰，必爆 | 能存 |
| 什么时候用 | n ≤ 1000 左右，要快速查"u、v 之间有没有边" | 几乎所有情况 |
⚠️
题目要求"有多个可走的点时，先走编号小的"（比如课堂题
P5318），要先把每个 g[u] 排序。
| 环节 | 题目 | 要点 |
|---|---|---|
| 课堂题 1 | P1157 组合的输出（橙） | 组合型 DFS；每个数占 3 个场宽
setw(3) |
| 课堂题 2 | P1219 八皇后（黄） | 列、两条对角线各开一个标记数组；对角线编号怎么算？ |
| 课堂题 3 | P1596 Lake Counting（橙） | 2.2 节，八个方向 |
| 课堂题 4 | P5318 查找文献（橙） | 2.3 节；同时输出 DFS 序和 BFS 序；邻居要排序 |
| 小测 1（20 分钟） | P1451 求细胞数量（橙） | 四个方向；输入是一串数字连在一起，怎么读？ |
| 小测 2（20 分钟） | P1618 三连击（升级版）（橙） | 全排列变形；题目保证 0 ≤ A，A 可能是 0，自造数据要包含这个 |
| 档 | 必做（4 道） | 选做 |
|---|---|---|
| B 档 | ① P1036 选数（橙，L06 讲过但从没交过） ② P5732
杨辉三角（红） ③ P1162 填涂颜色（橙，连通块） ④ P1443
马的遍历（橙，L07 讲过） |
P1135 奇怪的电梯（黄） |
| A 档 | ① P1162 填涂颜色（橙） ② P2822 组合数问题（黄，杨辉三角取模 + 二维前缀和） ③ P1141 01 迷宫（黄，连通块 + 多次询问） ④ P3916 图的遍历（黄，反着建图） | P1025 数的划分（黄，剪枝） |
break
剪掉后面所有分支，需要什么前提？g[u] 里的邻居"，其余不变。本次打卡：M9 ①、M10 ①（两道盲写）；作业 AC 后打 ②③。