深度优先搜索（DFS）与广度优先搜索（BFS）竞赛复习资料
1.1 DFS 与 BFS 算法概述
1.1.1 什么是搜索算法
搜索算法是一类用于遍历或搜索树/图的算法，按照一定的规则访问图中的每个节点恰好一次。在信息学竞赛中，搜索算法是解决组合优化、状态空间探索等问题的基础工具。搜索算法的核心思想是将问题抽象为一个“状态图”，通过系统地枚举可能的状态来寻找目标状态。
1.1.2 DFS 与 BFS 的核心区别
| 比较维度 |
DFS（深度优先搜索） |
BFS（广度优先搜索） |
| 数据结构 |
栈（系统栈/手动栈） |
队列 |
| 空间复杂度 |
O(h)，h 为递归深度 |
O(2h)，h 为搜索深度 |
| 最短路径 |
不保证最短 |
保证最短（无权图） |
| 适用场景 |
全排列、组合、回溯、连通块、状态空间探索 |
最短路径、最少步数、分层搜索、连通块 |
| 特点 |
一条路走到黑，走不通再回溯 |
层层扩散，逐层遍历 |
1.1.3 时间复杂度分析
- 邻接矩阵存储：DFS 与 BFS 均为 O(V2)，其中 V 为顶点数
- 邻接表存储：DFS 与 BFS 均为 O(V+E)，其中 E 为边数
对于网格图（如 n×m 的迷宫），时间复杂度通常为 O(n×m)，因为每个格子最多被访问一次。
1.2 深度优先搜索（DFS）详解
1.2.1 算法思想
深度优先搜索是一种利用回溯思想的搜索算法。它从起始节点开始，沿着一条路径尽可能深入地访问节点，当无法继续时，回溯到上一个节点，尝试其他未被访问的路径。整个过程反复进行，直到所有可达节点都被访问为止。
1.2.2 算法推演过程
以网格图的连通块搜索为例，设当前位于坐标 (x,y)：
第一步：将当前位置 (x,y) 标记为已访问。
第二步：枚举四个相邻方向（上下左右），计算相邻坐标 (nx,ny)。
第三步：对于每个相邻坐标，判断是否满足搜索条件（在边界内、未访问、符合题目要求）。若满足，则递归调用 DFS，进入 (nx,ny)。
第四步：递归返回后，自动回溯到上一层，继续尝试其他方向。
第五步：当所有方向都尝试完毕后，当前 DFS 调用结束，返回到上一层。
1.2.3 伪代码模板
以下给出深度优先搜索的通用伪代码模板，分为递归版本和非递归版本。
递归版 DFS 伪代码：
DFS(当前状态 s):
如果 s 是目标状态:
记录答案或进行相应处理
返回
标记 s 为已访问
对于 s 的每一个合法后继状态 t:
如果 t 未被访问且满足约束条件:
DFS(t)
（可选）撤销 s 的标记 // 如果需要回溯枚举所有方案
|
非递归版 DFS 伪代码（使用显式栈）：
DFS(起始状态 start):
初始化空栈 S
S.push(start)
标记 start 为已访问
当 S 非空:
u = S.top()
如果 u 还有未被访问的合法后继状态 v:
标记 v 为已访问
S.push(v)
否则:
S.pop() // 回溯
|
1.2.4 DFS 通用代码模板
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
i64 n, m;
cin >> n >> m;
vector<vector<i64>> a(n, vector<i64>(m));
vector<vector<i64>> vis(n, vector<i64>(m));
const i64 dx[4] = {0, 1, 0, -1};
const i64 dy[4] = {1, 0, -1, 0};
function<void(i64, i64)> dfs = [&](i64 x, i64 y) {
vis[x][y] = 1;
for (i64 i = 0; i < 4; i++) {
i64 nx = x + dx[i];
i64 ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && a[nx][ny] == 1) {
dfs(nx, ny);
}
}
};
i64 ans = 0;
for (i64 i = 0; i < n; i++) {
for (i64 j = 0; j < m; j++) {
if (!vis[i][j] && a[i][j] == 1) {
ans++;
dfs(i, j);
}
}
}
cout << ans << "\n";
return 0;
}
|
1.2.5 DFS 的关键要点
-
递归深度限制：DFS 使用系统栈，递归深度过大可能导致栈溢出。竞赛中默认栈空间通常为 8MB 至 256MB，递归深度约在 104 至 105 级别安全。对于深度更大的情况，需考虑改为非递归实现或使用迭代加深搜索。
-
回溯与状态恢复：当搜索需要枚举所有可能方案时，递归返回后必须恢复被修改的状态。例如在全排列问题中，需要将标记过的数字还原。
-
剪枝优化：在搜索过程中，若发现当前分支不可能产生更优解，可提前终止该分支的搜索，称为剪枝。常见的剪枝包括可行性剪枝和最优性剪枝。
1.3 广度优先搜索（BFS）详解
1.3.1 算法思想
广度优先搜索使用队列数据结构，从起始节点开始，按照与起点的距离逐层向外扩展搜索。BFS 的核心特性是逐层遍历，即先访问距离起点为 1 的所有节点，再访问距离为 2 的所有节点，以此类推。由于这种特性，BFS 在无权图中能够保证第一次到达目标节点时的路径就是最短路径。
1.3.2 算法推演过程
以网格图的最短路径搜索为例：
第一步：将起点 (sx,sy) 加入队列，并标记为已访问，距离设为 0。
第二步：当队列非空时，取出队首元素 (x,y) 及其当前距离 d。
第三步：枚举四个相邻方向，计算相邻坐标 (nx,ny)。若 (nx,ny) 等于终点，则返回 d+1。
第四步：对于每个相邻坐标，判断是否满足搜索条件（在边界内、未访问、非障碍物）。若满足，将其加入队列，标记为已访问，距离设为 d+1。
第五步：重复第二至第四步。若队列为空仍未找到终点，则说明不可达。
1.3.3 伪代码模板
以下给出广度优先搜索的通用伪代码模板，包含标准 BFS 和记录路径的变体。
标准 BFS 伪代码：
BFS(起始状态 start):
初始化空队列 Q
Q.push(start)
标记 start 为已访问
dist[start] = 0 // 可选，记录距离
当 Q 非空:
u = Q.front()
Q.pop()
对于 u 的每一个合法后继状态 v:
如果 v 未被访问且满足约束条件:
标记 v 为已访问
dist[v] = dist[u] + 1
Q.push(v)
如果 v 是目标状态:
返回 dist[v] // 找到最短距离
返回 未找到 // 目标状态不可达
|
带路径记录的 BFS 伪代码：
BFS_With_Path(起始状态 start, 目标状态 target):
初始化空队列 Q
Q.push(start)
标记 start 为已访问
prev[start] = null // 记录前驱状态
当 Q 非空:
u = Q.front()
Q.pop()
如果 u == target:
// 回溯构造路径
path = 空列表
cur = target
当 cur != null:
path.prepend(cur)
cur = prev[cur]
返回 path
对于 u 的每一个合法后继状态 v:
如果 v 未被访问且满足约束条件:
标记 v 为已访问
prev[v] = u
Q.push(v)
返回 未找到
|
1.3.4 BFS 通用代码模板
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
i64 n, m;
cin >> n >> m;
vector<string> grid(n);
for (i64 i = 0; i < n; i++) cin >> grid[i];
vector<vector<i64>> dist(n, vector<i64>(m, -1));
queue<pair<i64, i64>> q;
const i64 dx[4] = {0, 1, 0, -1};
const i64 dy[4] = {1, 0, -1, 0};
q.push({0, 0});
dist[0][0] = 0;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (i64 i = 0; i < 4; i++) {
i64 nx = x + dx[i];
i64 ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1 && grid[nx][ny] == '.') {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
cout << dist[n - 1][m - 1] << "\n";
return 0;
}
|
1.3.5 BFS 的关键要点
-
队列的 FIFO 特性：BFS 利用队列先进先出的特性保证逐层遍历。入队时标记已访问，防止重复入队。
-
最短路径保证：在边权均为 1 的图中，BFS 第一次访问到某节点时的距离即为最短距离。这是因为 BFS 按层扩展，当某节点首次被发现时，必然是通过最短路径到达的。
-
空间复杂度：BFS 需要存储当前层和下一层的节点，空间复杂度可达 O(bd)，其中 b 为分支因子，d 为深度。在状态空间较大时需谨慎使用。
1.4 DFS 经典例题
1.4.1 例题一：全排列问题
题目描述：给定一个正整数 n（n≤8），输出 1 到 n 的所有全排列，按字典序输出。
输入格式：一行一个整数 n。
输出格式：每行一个排列，数字之间用空格分隔。
样例输入：
样例输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
|
解法分析：这是 DFS 最基础的应用。用一个数组 vis 记录每个数字是否已被使用，用一个数组 path 记录当前构造的排列。DFS 递归到第 depth 层时，枚举所有未被使用的数字，将其加入 path，标记为已使用，递归进入下一层；递归返回后恢复标记。当 depth == n 时输出当前排列。
C++ 代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
i64 n;
cin >> n;
vector<i64> vis(n + 1, 0);
vector<i64> path(n);
function<void(i64)> dfs = [&](i64 depth) {
if (depth == n) {
for (i64 i = 0; i < n; i++) {
cout << path[i] << (i == n - 1 ? "\n" : " ");
}
return;
}
for (i64 i = 1; i <= n; i++) {
if (!vis[i]) {
vis[i] = 1;
path[depth] = i;
dfs(depth + 1);
vis[i] = 0;
}
}
};
dfs(0);
return 0;
}
|
1.4.2 例题二：拆分自然数
题目描述：任何一个大于 1 的自然数 N，总可以拆分成若干个小于 N 的自然数之和。例如当 N=3 时，有两种划分，即 3=1+2 和 3=1+1+1。试求出 N 的所有拆分方案。
输入格式：一个整数 N（1<N<49）。
输出格式：输出每一种划分方案（无分先后），每种划分方案占一行，最后一行为方案总数。
样例输入：
样例输出：
解法分析：本题要求将一个整数拆分成若干个正整数之和，且拆分出的数字非严格递增（避免重复）。这属于经典的整数划分问题，可使用 DFS 回溯求解。
- 用一个数组
ans 记录当前拆分出的数字序列，ans[0] 初始化为 1 便于后续比较。
- DFS 函数
dfs(k, last) 中，参数 k 表示当前要填的位置（从 1 开始），last 表示剩余待拆分的数值。
- 每次枚举当前数字 i，范围从
ans[k - 1] 到 last（保证非递减，避免重复方案）。
- 将 i 放入
ans[k]，递归调用 dfs(k + 1, last - i)。
- 递归边界：当
last == 0 且 k>2 时（即至少拆成两个数，若只拆成一个数等于自身不合法），输出一种方案并计数。
C++ 代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
i64 n, cnt = 0;
cin >> n;
vector<i64> ans(50, 1);
auto print = [&](i64 k) -> void {
cout << n << "=";
for (i64 i = 1; i < k; i++) {
cout << ans[i] << "+\n"[i == (i64)k - 1];
}
};
function<void(i64, i64)> dfs = [&](i64 k, i64 last) -> void {
if (last == 0 && k > 2) {
print(k);
cnt++;
return;
} else {
for (i64 i = ans[k - 1]; i <= last; i++) {
ans[k] = i;
dfs(k + 1, last - i);
}
}
};
dfs(1, n);
cout << cnt << "\n";
return 0;
}
|
1.4.3 例题三：瓷砖计数（网格连通块）
题目描述：在一个 w×h 的矩形广场上，每一块 1×1 的地面都铺设了红色或黑色的瓷砖。小林同学站在某一块黑色的瓷砖上，他可以从此处出发，移动到上、下、左、右四个相邻的且是黑色的瓷砖上。现在，他想知道，通过重复上述移动所能经过的黑色瓷砖数。
输入格式：第 1 行为 h、w，2≤w,h≤50，之间由一个空格隔开；以下为一个 w 行 h 列的二维字符矩阵，每个字符为 . # @，分别表示该位置为黑色的瓷砖、红色的瓷砖、小林的初始位置。
输出格式：输出一行一个整数，表示小林从初始位置出发经过的黑色瓷砖数。
样例输入：
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
|
样例输出：
解法分析：这是典型的 DFS 连通块计数问题。从起点 @ 开始，向四个方向搜索黑色瓷砖 .，每走到一块新的黑色瓷砖就计数一次，并标记已访问防止重复。由于只需求可达的黑色瓷砖总数，DFS 与 BFS 均可，DFS 代码更简洁。
C++ 代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
i64 h, w;
cin >> h >> w;
vector<string> g(w);
for (auto &s : g) cin >> s;
i64 sx = -1, sy = -1;
for (i64 i = 0; i < w && sx == -1; i++)
for (i64 j = 0; j < h && sx == -1; j++)
if (g[i][j] == '@') sx = i, sy = j;
vector<vector<bool>> vis(w, vector<bool>(h, false));
vector<i64> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
i64 ans = 0;
function<void(i64, i64)> dfs = [&](i64 x, i64 y) {
vis[x][y] = true;
ans++;
for (i64 i = 0; i < 4; i++) {
i64 nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= w || ny < 0 || ny >= h || vis[nx][ny] || g[nx][ny] == '#') continue;
dfs(nx, ny);
}
};
dfs(sx, sy);
cout << ans << "\n";
}
|
1.4.4 例题四：n-皇后问题（AcWing 843 / 经典 DFS 剪枝）
题目描述：在 n×n 的国际象棋棋盘上放置 n 个皇后，使得它们互不攻击（任意两个皇后不在同一行、同一列或同一对角线上）。输出所有可能的方案，按字典序输出。
输入格式：一行一个整数 n（1≤n≤9）。
输出格式：每行一个方案，用 n 个数字表示，第 i 个数字表示第 i 行的皇后放在第几列。
样例输入：
样例输出：
解法分析：逐行放置皇后，每行只需选择一个列。用三个数组分别标记当前列、主对角线、副对角线是否已被占用。主对角线的编号为 i+j，副对角线的编号为 i−j+n。DFS 递归到第 row 行时，枚举所有未被占用的列，放置皇后并更新标记，然后递归到下一行；递归返回后恢复标记。当 row == n 时输出方案。
C++ 代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
i64 n;
cin >> n;
vector<i64> col(n + 1, 0), dg(2 * n + 1, 0), udg(2 * n + 1, 0);
vector<i64> ans(n);
function<void(i64)> dfs = [&](i64 row) {
if (row == n) {
for (i64 i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
return;
}
for (i64 j = 1; j <= n; j++) {
if (!col[j] && !dg[row + j] && !udg[row - j + n]) {
col[j] = dg[row + j] = udg[row - j + n] = 1;
ans[row] = j;
dfs(row + 1);
col[j] = dg[row + j] = udg[row - j + n] = 0;
}
}
};
dfs(0);
return 0;
}
|
1.4.5 例题五：P1019 单词接龙（NOIP2000 提高组第三题）
题目描述：单词接龙是一个类似成语接龙的游戏。已知一组单词，给定一个起始字母，要求找出以该字母开头的最长的“龙”。每个单词在“龙”中最多出现两次。两个单词连接时，重叠部分合为一部分，且相邻部分不能存在包含关系。
输入格式：第一行为一个整数 n（n≤20）表示单词数量。接下来 n 行每行一个单词。最后一行一个字符表示起始字母。
输出格式：输出最长“龙”的长度。
样例输入：
样例输出：
样例说明：连续的“龙”为 atoucheatactactouchoose。
解法分析：这是一道经典的 NOIP 提高组 DFS 真题。首先预处理任意两个单词的重叠长度 overlap[i][j]，表示将单词 j 接在单词 i 后面时的最小重叠长度。预处理时从单词 i 的末尾向前遍历，找与单词 j 开头相同的部分，取最小重叠（题目要求尽可能短的重叠）。然后从以起始字母开头的单词开始 DFS，用 used 数组记录每个单词的使用次数（不能超过两次），每次尝试将未使用满两次且存在有效重叠的单词接在当前单词后面，更新答案并递归。递归返回时恢复使用次数。
C++ 代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
i64 n;
cin >> n;
vector<string> a(n);
for (i64 i = 0; i < n; i++) cin >> a[i];
char start;
cin >> start;
vector<vector<i64>> overlap(n, vector<i64>(n, 0));
for (i64 i = 0; i < n; i++) {
for (i64 j = 0; j < n; j++) {
string &s1 = a[i], &s2 = a[j];
i64 len1 = s1.size(), len2 = s2.size();
for (i64 k = 1; k < min(len1, len2); k++) {
if (s1.substr(len1 - k) == s2.substr(0, k)) {
overlap[i][j] = k;
break;
}
}
}
}
vector<i64> used(n, 0);
i64 ans = 0;
function<void(i64, i64)> dfs = [&](i64 cur, i64 len) {
ans = max(ans, len);
for (i64 nxt = 0; nxt < n; nxt++) {
if (used[nxt] < 2 && overlap[cur][nxt] > 0) {
used[nxt]++;
dfs(nxt, len + a[nxt].size() - overlap[cur][nxt]);
used[nxt]--;
}
}
};
for (i64 i = 0; i < n; i++) {
if (a[i][0] == start) {
used[i]++;
dfs(i, a[i].size());
used[i]--;
}
}
cout << ans << "\n";
return 0;
}
|
1.4.6 例题六：P1605 迷宫（求方案数）
题目描述：给定一个 N×M 的迷宫，用 0 表示空地，1 表示障碍物。起点为 (SX,SY)，终点为 (FX,FY)。每次只能上下左右移动一格。求从起点到终点的方案总数。
输入格式：第一行 N M T（N,M≤5，T 为障碍物数量）。第二行 SX SY FX FY。接下来 T 行每行一个障碍物坐标。
输出格式：一行一个整数，表示方案总数。
样例输入：
样例输出：
解法分析：由于 N,M≤5，状态空间很小，直接用 DFS 枚举所有路径即可。用 vis 数组标记已走过的格子防止重复访问。从起点开始 DFS，每步向四个方向移动，若到达终点则计数加一。递归返回前需要恢复 vis 标记（回溯）。
C++ 代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
i64 n, m, t;
cin >> n >> m >> t;
i64 sx, sy, fx, fy;
cin >> sx >> sy >> fx >> fy;
sx--, sy--, fx--, fy--;
vector<vector<i64>> g(n, vector<i64>(m, 0));
vector<vector<i64>> vis(n, vector<i64>(m, 0));
for (i64 i = 0; i < t; i++) {
i64 x, y;
cin >> x >> y;
x--, y--;
g[x][y] = 1;
}
const i64 dx[4] = {0, 1, 0, -1};
const i64 dy[4] = {1, 0, -1, 0};
i64 ans = 0;
function<void(i64, i64)> dfs = [&](i64 x, i64 y) {
if (x == fx && y == fy) {
ans++;
return;
}
for (i64 i = 0; i < 4; i++) {
i64 nx = x + dx[i];
i64 ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && !g[nx][ny]) {
vis[nx][ny] = 1;
dfs(nx, ny);
vis[nx][ny] = 0;
}
}
};
vis[sx][sy] = 1;
dfs(sx, sy);
cout << ans << "\n";
return 0;
}
|
1.4.7 例题七：P5022 旅行（NOIP2018 提高组）
题目描述：给定一个 n 个点 m 条边的连通无向图（m=n−1 或 m=n），要求从 1 号点出发，每次走一条未走过的边，访问所有点恰好一次，求字典序最小的访问顺序。
输入格式：第一行 n m。接下来 m 行每行两个整数 u,v。
输出格式：一行 n 个整数，表示字典序最小的访问顺序。
解法分析：这道题是 NOIP2018 提高组的 DFS 难题。分两种情况：
C++ 代码（基环树版本）：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
i64 n, m;
cin >> n >> m;
vector<vector<i64>> g(n + 1);
vector<pair<i64, i64>> edges;
for (i64 i = 0; i < m; i++) {
i64 u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
edges.push_back({u, v});
}
for (i64 i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
vector<i64> best;
vector<i64> path;
vector<i64> vis(n + 1, 0);
i64 del_u = 0, del_v = 0;
function<void(i64)> dfs = [&](i64 u) {
vis[u] = 1;
path.push_back(u);
for (i64 v : g[u]) {
if ((u == del_u && v == del_v) || (u == del_v && v == del_u)) continue;
if (!vis[v]) dfs(v);
}
};
auto better = [&](vector<i64> &a, vector<i64> &b) {
for (i64 i = 0; i < n; i++) {
if (a[i] != b[i]) return a[i] < b[i];
}
return false;
};
if (m == n - 1) {
dfs(1);
best = path;
} else {
best.assign(n, n + 1);
for (auto &e : edges) {
del_u = e.first, del_v = e.second;
fill(vis.begin(), vis.end(), 0);
path.clear();
dfs(1);
if (path.size() == n && better(path, best)) best = path;
}
}
for (i64 i = 0; i < n; i++) cout << best[i] << " \n"[i == n - 1];
return 0;
}
|
1.5 BFS 经典例题
1.5.1 例题一：P1443 马的遍历
题目描述：给定一个 n×m 的棋盘，马从 (x,y) 出发，按照象棋马的走法（走“日”字），求马到达棋盘上每个点的最少步数。若无法到达，输出 −1。
输入格式：一行四个整数 n m x y。
输出格式：n 行 m 列，每个位置的答案，左对齐，宽度 5。
样例输入：
样例输出：
解法分析：典型的 BFS 求最短步数问题。马的走法有 8 个方向：(1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1), (-2,1), (-2,-1)。从起点开始 BFS，用 dist 数组记录到达每个位置的最少步数（初始化为 −1）。每次从队列取出一个位置，枚举 8 个方向，若新位置在棋盘内且未访问过，则更新步数并入队。
C++ 代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
i64 n, m, sx, sy;
cin >> n >> m >> sx >> sy;
sx--, sy--;
vector<vector<i64>> dist(n, vector<i64>(m, -1));
queue<pair<i64, i64>> q;
const i64 dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const i64 dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};
q.push({sx, sy});
dist[sx][sy] = 0;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (i64 i = 0; i < 8; i++) {
i64 nx = x + dx[i];
i64 ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
for (i64 i = 0; i < n; i++) {
for (i64 j = 0; j < m; j++) {
cout << left << setw(5) << dist[i][j];
}
cout << "\n";
}
return 0;
}
|
1.5.2 例题二：P1135 奇怪的电梯
题目描述：有一栋 N 层的大楼，电梯在第 i 层只能向上或向下移动 Ki 层。求从 A 层到 B 层最少需要按几次按钮。若无法到达，输出 −1。
输入格式：第一行三个整数 N A B。第二行 N 个整数 K1,K2,…,KN。
输出格式：一行一个整数，最少按键次数；若无法到达，输出 −1。
样例输入：
样例输出：
解法分析：将每层楼看作图中的一个节点，从第 i 层可以走到第 i+Ki 层和第 i−Ki 层（如果存在）。求从 A 到 B 的最短路径，BFS 即可。用 dist 数组记录到达每层的最少步数，初始化为 −1。
C++ 代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
i64 n, a, b;
cin >> n >> a >> b;
vector<i64> k(n + 1);
for (i64 i = 1; i <= n; i++) cin >> k[i];
vector<i64> dist(n + 1, -1);
queue<i64> q;
q.push(a);
dist[a] = 0;
while (!q.empty()) {
i64 u = q.front();
q.pop();
if (u == b) break;
for (i64 delta : {k[u], -k[u]}) {
i64 v = u + delta;
if (v >= 1 && v <= n && dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
cout << dist[b] << "\n";
return 0;
}
|
1.5.3 例题三：P1162 填涂颜色（BFS 染色）
题目描述：由数字 0 组成的方阵中，有一个任意形状的闭合圈，闭合圈由数字 1 构成。要求将闭合圈内的所有 0 替换为 2，其余部分不变。
输入格式：第一行一个整数 n（5≤n≤30）。接下来 n 行每行 n 个整数（0 或 1）。
输出格式：n 行，每行 n 个整数，表示处理后的方阵。
解法分析：这是一道典型的“被围绕区域”问题。闭合圈内的 0 无法从边界到达。思路：从方阵的四周边界上的 0 开始 BFS/DFS，将所有能到达的 0 标记为已访问。最后遍历整个方阵，未被访问的 0 就是闭合圈内的，将其改为 2。这样避免了复杂的闭合圈检测。
C++ 代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
i64 n;
cin >> n;
vector<vector<i64>> a(n, vector<i64>(n));
vector<vector<i64>> vis(n, vector<i64>(n, 0));
for (i64 i = 0; i < n; i++) {
for (i64 j = 0; j < n; j++) {
cin >> a[i][j];
}
}
const i64 dx[4] = {0, 1, 0, -1};
const i64 dy[4] = {1, 0, -1, 0};
queue<pair<i64, i64>> q;
for (i64 i = 0; i < n; i++) {
if (a[i][0] == 0) { q.push({i, 0}); vis[i][0] = 1; }
if (a[i][n - 1] == 0) { q.push({i, n - 1}); vis[i][n - 1] = 1; }
if (a[0][i] == 0) { q.push({0, i}); vis[0][i] = 1; }
if (a[n - 1][i] == 0) { q.push({n - 1, i}); vis[n - 1][i] = 1; }
}
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (i64 i = 0; i < 4; i++) {
i64 nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && !vis[nx][ny] && a[nx][ny] == 0) {
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
for (i64 i = 0; i < n; i++) {
for (i64 j = 0; j < n; j++) {
if (a[i][j] == 0 && !vis[i][j]) a[i][j] = 2;
cout << a[i][j] << " \n"[j == n - 1];
}
}
return 0;
}
|
1.5.4 例题四：P1032 字串变换（NOIP2002 提高组 / 双向 BFS）
题目描述：已知有两个字符串 A,B 及一组字串变换规则（至多 6 条）：A1→B1,A2→B2,…。求在 10 步以内将 A 变为 B 的最少步数，若超过 10 步或无法变换，输出 NO ANSWER!。
输入格式：第一行 A B。接下来若干行，每行一条规则 Ai Bi。
输出格式：最少步数或 NO ANSWER!。
解法分析：这是 NOIP2002 提高组的经典题目，也是双向 BFS 的入门例题。单向 BFS 的状态数增长极快，分支因子最大为 6，深度为 10 时状态数可达 610 级别，会超时。双向 BFS 从起点和终点同时搜索，每次选择状态数较少的方向扩展一步，当两个方向的搜索相遇时即找到最短路径。双向 BFS 将深度减半，状态数大幅减少。
C++ 代码：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
string a, b;
cin >> a >> b;
vector<pair<string, string>> rules;
string x, y;
while (cin >> x >> y) rules.push_back({x, y});
if (a == b) { cout << "0\n"; return 0; }
unordered_map<string, i64> da, db;
queue<string> qa, qb;
qa.push(a); da[a] = 0;
qb.push(b); db[b] = 0;
auto extend = [&](queue<string> &q, unordered_map<string, i64> &d1,
unordered_map<string, i64> &d2, bool forward) -> i64 {
i64 sz = q.size();
for (i64 cnt = 0; cnt < sz; cnt++) {
string cur = q.front();
q.pop();
i64 step = d1[cur];
for (auto &rule : rules) {
string from = forward ? rule.first : rule.second;
string to = forward ? rule.second : rule.first;
size_t pos = 0;
while ((pos = cur.find(from, pos)) != string::npos) {
string nxt = cur;
nxt.replace(pos, from.size(), to);
if (d2.count(nxt)) return step + 1 + d2[nxt];
if (!d1.count(nxt)) {
d1[nxt] = step + 1;
q.push(nxt);
}
pos++;
}
}
}
return -1;
};
i64 ans = -1;
while (!qa.empty() && !qb.empty()) {
if (qa.size() <= qb.size()) ans = extend(qa, da, db, true);
else ans = extend(qb, db, da, false);
if (ans != -1) break;
if (da.size() + db.size() > 1000000) break;
}
if (ans != -1 && ans <= 10) cout << ans << "\n";
else cout << "NO ANSWER!\n";
return 0;
}
|
1.5.5 例题五：P1979 华容道（NOIP2013 提高组 / BFS + 最短路）
题目描述：在一个 n×m 的棋盘上，有若干个空格和一个目标棋子。每次可以将空格与相邻的棋子交换位置。给定初始状态，求将目标棋子移动到指定位置的最少步数。
输入格式：第一行 n m q。接下来 n 行每行 m 个整数表示棋盘（0 为空格，1 为棋子）。接下来 q 行每行 6 个整数表示空格位置、目标棋子位置、目标位置。
输出格式：q 行，每行一个整数表示最少步数，无法完成输出 −1。
解法分析：NOIP2013 提高组压轴题，难度较高。核心在于状态设计：目标棋子的移动依赖于空格的位置。设目标棋子位置为 (i,j)，空格在其上下左右四个方向，共有 4×n×m 种状态。状态转移分两步：先用 BFS 计算空格从一个方向移动到另一个方向的最小步数（预处理），再用 BFS 或最短路算法（如 SPFA/Dijkstra）计算状态之间的转移。最终答案即为初始状态到目标状态的最短距离。
由于篇幅限制，此处仅提供核心思路，完整代码可参考洛谷 P1979 题解区。
1.6 经典竞赛真题精选
1.6.1 广州市信息学竞赛真题精选
由于各校选拔试题较少公开，以下整理广州市信息学竞赛及广东省选中的经典搜索题目。
广州二中 / 六中 / 广雅 / 省实 / 广大附中 / 华附 选拔常见题型：
各校选拔通常涵盖以下类型：
- 连通块计数（如岛屿数量、全球变暖）
- 迷宫最短路径
- 全排列与组合枚举
- 图的遍历（DFS 序与 BFS 序）
- 状态空间搜索
推荐练习题目：
| 题目编号 |
题目名称 |
来源 |
考点 |
难度 |
| P1451 |
细胞数量 |
洛谷 |
连通块 / DFS / BFS |
★☆☆ |
| P1332 |
血色先锋队 |
洛谷 |
BFS 多源最短路径 |
★★☆ |
| P1746 |
离开中山路 |
洛谷 |
BFS 最短路 |
★★☆ |
| P1747 |
好奇怪的游戏 |
洛谷 |
BFS 状态搜索 |
★★☆ |
| P1825 |
Corn Maze S |
USACO |
BFS 传送门 |
★★☆ |
| P2895 |
Meteor Shower S |
USACO |
BFS 动态障碍 |
★★★ |
第九届蓝桥杯省赛B组：全球变暖
题目描述：给定一个 n×n 的网格照片，# 表示陆地，. 表示海洋。上下左右相邻的陆地构成一个岛屿。由于全球变暖，如果一个陆地格子的四个方向不全是陆地，它将被淹没。求完全被淹没的岛屿数量（即岛上没有不会被淹没的陆地）。
输入格式：第一行一个整数 n。接下来 n 行每行一个长度为 n 的字符串。
输出格式：一个整数表示完全被淹没的岛屿数。
解法分析：用 DFS 或 BFS 遍历每个岛屿（连通块），在遍历过程中统计该岛屿上“不会被淹没的陆地”数量（即四个方向都是陆地的格子）。若某个岛屿上没有这样的格子，则它会被完全淹没，答案加一。
1.6.2 NOIP 历年真题精选
| 年份 |
题目名称 |
洛谷题号 |
考点 |
难度 |
| 2000 |
单词接龙 |
P1019 |
DFS / 字符串处理 |
★★☆ |
| 2002 |
字串变换 |
P1032 |
双向 BFS |
★★★ |
| 2004 |
火星人 |
P1088 |
DFS 全排列 |
★★☆ |
| 2005 |
采药 |
P1048 |
记忆化搜索 / 01背包 |
★★☆ |
| 2008 |
传纸条 |
P1006 |
记忆化搜索 / DP |
★★★ |
| 2013 |
华容道 |
P1979 |
BFS + 状态设计 |
★★★★ |
| 2018 |
旅行 |
P5022 |
DFS / 基环树 |
★★★ |
1.6.3 CSP-J/S 历年真题精选
| 年份 |
题目名称 |
洛谷题号 |
考点 |
难度 |
| 2019 J |
加工零件 |
P5663 |
BFS 奇偶性 |
★★☆ |
| 2020 J |
方格取数 |
P7074 |
记忆化搜索 / DP |
★★☆ |
| 2021 J |
网络连接 |
P7911 |
模拟 / 字符串 |
★★☆ |
| 2022 J |
上升点列 |
P8816 |
DP / 状态设计 |
★★☆ |
| 2023 J |
公路 |
P9749 |
贪心 / 模拟 |
★★☆ |
| 2019 S |
树的重心 |
P5666 |
树形 DP / DFS |
★★★★ |
| 2021 S |
回文 |
P7915 |
贪心 / 构造 |
★★★ |
| 2023 S |
消消乐 |
P9753 |
哈希 / 栈 |
★★★ |
1.7 优化技巧与注意事项
1.7.1 DFS 优化技巧
1. 剪枝
剪枝是在搜索过程中提前排除不可能产生更优解的分支，大幅减少搜索空间。
- 可行性剪枝：若当前状态已无法满足题目要求，则剪掉。例如在排列问题中，若发现当前部分排列已违背条件，直接返回。
- 最优性剪枝：若当前状态的代价已超过已知的最优解，则剪掉。例如在求最小代价的问题中，用全局变量记录当前最优解，若当前搜索深度已超过该值，直接返回。
- 对称性剪枝：若存在对称状态，只需搜索其中之一。例如在 n-皇后问题中，可以只搜索一半的棋盘。
2. 记忆化搜索
对于有重叠子问题的搜索，用数组记录已计算过的结果，避免重复计算。常用于动态规划问题的递归实现。例如在计算斐波那契数列或树形 DP 时。
3. 迭代加深搜索（IDDFS）
当搜索深度未知时，逐层增加深度限制进行 DFS。结合了 DFS 的空间优势和 BFS 的最优性。常用于状态空间极大但最优解深度较小的题目。
4. 双向搜索（Meet in the Middle）
将搜索空间分成两半，分别搜索并存储结果，最后合并。将复杂度从 O(bd) 降为 O(bd/2)。
1.7.2 BFS 优化技巧
1. 双向 BFS
从起点和终点同时开始 BFS，每次选择状态较少的一端扩展。当两端相遇时即找到最优解。适用于分支因子较大的最短路径问题，如字串变换（NOIP2002）。
2. A 算法（启发式搜索）*
在 BFS 的基础上引入启发函数 h(n) 估计当前状态到目标状态的距离，优先扩展 f(n)=g(n)+h(n) 最小的状态。其中 g(n) 为已走步数，h(n) 为启发式估计值。要求 h(n) 不能高估实际距离（可采纳性）。
3. 0-1 BFS
当图中的边权只有 0 和 1 时，使用双端队列（deque）代替普通队列。遇到权为 0 的边时插入队首，权为 1 的边插入队尾。这样保证队列始终按距离排序，时间复杂度 O(V+E)。
1.7.3 常见错误与注意事项
- 全局数组清零：多组测试数据时，务必重置
vis 数组和 dist 数组。
- 入队前标记：BFS 中必须在入队时立即标记已访问，而非出队时。否则同一节点可能被多次入队，导致队列爆炸。
- 边界条件：网格图搜索时，注意下标从 0 还是 1 开始，以及边界检查的正确性。
- 递归深度：DFS 递归深度过大时，考虑使用手动栈或改用 BFS。
- 方向数组顺序：在某些题目中，方向数组的枚举顺序会影响字典序，需根据题目要求调整。
- 空间优化：对于大型网格图（如 n,m≤103），优先使用
vector<vector<T>> 或一维数组模拟二维，避免原生二维数组的大小限制。
1.7.4 选择 DFS 还是 BFS 的决策指南
| 问题特征 |
推荐算法 |
原因 |
| 求最短路径 / 最少步数（无权图） |
BFS |
BFS 保证第一次到达即为最短 |
| 求所有可行方案 |
DFS |
DFS 天然支持回溯枚举所有状态 |
| 状态空间极大、深度未知 |
迭代加深 DFS |
结合 DFS 的空间优势 |
| 连通块计数 |
DFS 或 BFS |
两者均可，DFS 代码更简洁 |
| 需要剪枝优化 |
DFS |
DFS 更容易实现各种剪枝策略 |
| 分层处理 |
BFS |
BFS 天然按层遍历 |
| 有环图的遍历 |
DFS 或 BFS |
均需 vis 数组防止重复访问 |
| 拓扑排序 |
BFS（Kahn）或 DFS |
DFS 后序遍历也可以实现 |
1.8 总结
深度优先搜索（DFS）和广度优先搜索（BFS）是信息学竞赛中最基础也是最重要的两类搜索算法。DFS 以“一条路走到黑”的回溯思想擅长枚举所有可能状态，适合排列组合、路径方案计数等场景；BFS 以“层层扩散”的方式保证在无权图中找到最短路径，适合求最少步数、最短距离等场景。
在竞赛中，纯暴力搜索往往难以通过大数据，需要结合剪枝、记忆化、双向搜索、启发式搜索等优化技巧。对于不同的问题特征，需要灵活选择合适的算法及其变体。
推荐学习路径：
- 先掌握 DFS 与 BFS 的基础模板，理解递归回溯与队列的核心思想
- 通过网格图类题目（迷宫、连通块）熟练两种算法的实现
- 学习剪枝技巧（n-皇后、数独等经典问题）
- 学习 BFS 的变体（双向 BFS、0-1 BFS、A*）
- 挑战 NOIP/CSP 真题中的搜索综合题（如 P5022 旅行、P1979 华容道）
参考资料：
- 洛谷题单：搜索算法入门、DFS 与 BFS 专题
- 《信息学奥赛一本通（C++版）》搜索章节
- OI-Wiki：深度优先搜索、广度优先搜索
- AcWing 算法基础课：搜索与图论
