第4章搜索算法

🎯 本章学习目标

通过本章的学习，你将能够：

理解DFS思想：掌握深度优先搜索的核心——一条路走到黑，碰壁回头
实现DFS：能用递归和栈两种方式实现深度优先搜索
理解BFS思想：掌握广度优先搜索的核心——层序扩散，先近后远
实现BFS：能用队列实现广度优先搜索
对比DFS和BFS：清楚两者的区别、适用场景和时间空间复杂度
掌握回溯法：理解DFS中的回溯思想（选择-递归-撤销）
解决迷宫问题：能用DFS或BFS解决迷宫路径、最短路径问题
二叉树搜索：掌握二叉树的DFS遍历和BFS层序遍历
标记访问状态：掌握visited数组和距离数组的使用
应对真题题型：能解决选择、代码填空、编程等各类搜索题目

🗺️ 本章知识图谱

搜索算法
├── DFS 深度优先搜索
│   ├── 核心思想：一条路走到黑，碰壁回头
│   ├── 实现方式
│   │   ├── 递归实现（最常用）
│   │   └── 栈实现
│   ├── 回溯思想
│   │   ├── 选择 → 递归 → 撤销
│   │   └── 恢复现场
│   ├── 适用场景
│   │   ├── 所有路径/方案数
│   │   ├── 排列组合问题
│   │   └── 状态空间搜索
│   └── 复杂度
│       ├── 时间：O(状态数)
│       └── 空间：O(深度)（递归栈）
├── BFS 广度优先搜索
│   ├── 核心思想：层序扩散，先近后远
│   ├── 实现方式：队列
│   ├── 适用场景
│   │   ├── 最短路径（无权图）
│   │   ├── 层序遍历
│   │   └── 扩散问题
│   ├── 距离数组 dist[]
│   │   ├── 初始值 -1（未访问）
│   │   └── dist[邻居] = dist[当前] + 1
│   └── 复杂度
│       ├── 时间：O(状态数)
│       └── 空间：O(状态数)（队列）
├── DFS vs BFS 对比
│   ├── 数据结构：栈 vs 队列
│   ├── 空间：DFS通常更省
│   ├── 最短路径：BFS擅长
│   └── 所有方案：DFS擅长
├── 常见应用
│   ├── 迷宫问题
│   │   ├── 能否到达：DFS/BFS都可以
│   │   └── 最短路径：BFS
│   ├── 二叉树遍历
│   │   ├── 前/中/后序：DFS
│   │   └── 层序：BFS
│   ├── 全排列/子集（回溯）
│   └── 连通块问题（flood fill）
└── 关键技巧
    ├── visited 数组标记访问
    ├── 方向数组 dx/dy
    ├── 边界判断
    └── 剪枝优化

一、DFS 深度优先搜索

🔍 核心思想

一条路走到黑，走不通就回头。

DFS（Depth First Search）的策略是：从起点出发，沿某条路径一直深入，直到无法继续（到达终点或碰到死路），然后回溯到上一个分叉点，换一条路继续探索。

🎨 生活类比

走迷宫时，你选定一个方向一直走，遇到死胡同就退回到最近的岔路口，换一条路再走——这就是 DFS。

📐 算法流程

DFS(当前状态):
    ① 检查是否满足终止条件 → 满足则记录答案/返回
    ② 标记当前状态为"已访问"
    ③ 枚举所有可能的下一步
        → 对每个合法且未访问的下一步：
            DFS(下一步状态)
    ④ 回溯：取消当前状态的访问标记（若需要复用状态）

🧩 递归实现模板（最常用）

cpp

bool visited[MAXN];  // 访问标记数组

void dfs(int cur) {
    if (/* 终止条件 */) {
        // 记录答案或更新最优解
        return;
    }
    visited[cur] = true;  // 标记已访问
    for (int nxt : adj[cur]) {  // 遍历所有邻居/可选方向
        if (!visited[nxt]) {
            dfs(nxt);
        }
    }
    // visited[cur] = false;  // 回溯时需要恢复标记的场景才取消注释
}

🧩 栈实现模板（非递归）

当递归深度过大可能导致栈溢出时，可以用显式栈模拟递归过程：

cpp

void dfs_stack(int start) {
    stack<int> st;
    st.push(start);
    visited[start] = true;

    while (!st.empty()) {
        int cur = st.top();
        st.pop();

        // 处理当前节点
        cout << cur << " ";

        // 将未访问的邻居入栈
        for (int nxt : adj[cur]) {
            if (!visited[nxt]) {
                visited[nxt] = true;
                st.push(nxt);
            }
        }
    }
}

⚠️ 易错点：非递归 DFS 中，入栈时就要标记 visited，而非出栈时才标记。否则同一节点可能被重复入栈多次，导致结果错误或 TLE。

📌 应用场景

场景	说明
迷宫求解	从入口 DFS 到出口，记录可行路径
连通性判断	从某点 DFS，看能访问到多少节点/格子
全排列/组合	枚举所有可能的排列组合方案
路径搜索	寻找从 A 到 B 的任意一条路径
连通块计数	统计图中有几个连通分量

✂️ 剪枝思想

DFS 的核心优化就是剪枝——在搜索过程中，提前判断某个分支不可能产生合法解，直接跳过，避免无意义的搜索。

常见剪枝策略：

剪枝类型	说明	示例
可行性剪枝	当前状态已经不满足约束条件，直接返回	数独中某格填入后导致冲突
最优性剪枝	当前代价已超过已知最优解，不再搜索	求最短路时当前步数已超过最优
去重剪枝	避免搜索等价的重复状态	组合问题中限制选取的单调递增

cpp

// 最优性剪枝示例
void dfs(int cur, int cost) {
    if (cost >= best_ans) return;  // 剪枝：当前代价已不优于最优解
    if (cur == target) {
        best_ans = min(best_ans, cost);
        return;
    }
    // ...继续搜索
}

二、BFS 广度优先搜索

🔍 核心思想

层层扩展，像水波纹一样向外扩散。

BFS（Breadth First Search）的策略是：从起点出发，先访问所有距离为 1 的邻居，再访问距离为 2 的邻居……逐层向外扩展，第一次到达目标时的层数就是最短距离。

🎨 生活类比

往平静的水面扔一颗石子，波纹从中心一圈一圈向外扩散——这就是 BFS。

📐 算法流程

BFS(起点):
    ① 起点入队，标记已访问
    ② 当队列非空时循环：
        a. 取出队首元素
        b. 处理当前元素
        c. 将所有合法且未访问的邻居入队，标记已访问
    ③ 结束

🧩 队列实现模板

cpp

int dist[MAXN];       // 记录距离（步数）
bool visited[MAXN];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    dist[start] = 0;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        // 处理当前节点
        cout << cur << " ";

        for (int nxt : adj[cur]) {
            if (!visited[nxt]) {
                visited[nxt] = true;
                dist[nxt] = dist[cur] + 1;  // 距离 +1
                q.push(nxt);
            }
        }
    }
}

📌 应用场景

场景	说明
无权图最短路径	BFS 第一次到达某点时的距离就是最短距离
层序遍历	二叉树按层遍历的天然工具
最少步数问题	求从初始状态到目标状态的最少操作次数
连通块大小	统计从某点出发能到达的所有节点

💡 BFS 的关键性质

在边权为 1 的图中，BFS 保证第一次到达某节点时经过的路径就是最短路径。

这是 BFS 最核心的价值。一旦某个节点被标记为 visited 并出队，它的最短距离就确定了，后续不可能找到更短的路径。

三、DFS vs BFS 对比

维度	DFS	BFS
数据结构	递归（系统栈）/ 显式栈	队列
搜索顺序	一条路走到黑再回头	逐层扩展
空间复杂度	O(最大深度)	O(最大宽度)
最短路径	❌ 不能保证最短	✅ 无权图保证最短
适用场景	遍历所有方案、判断连通性、回溯	最少步数、层序遍历、最短路径
实现难度	递归写法简洁	需要队列，稍复杂

四、二叉树的搜索算法

🌲 三种深度遍历

二叉树的 DFS 遍历根据根节点的访问顺序不同，分为三种：

遍历方式	访问顺序	结果
前序遍历（根-左-右）	A → B → D → E → C	先访问根
中序遍历（左-根-右）	D → B → E → A → C	根在中间
后序遍历（左-右-根）	D → E → B → C → A	最后访问根

🧩 代码实现

cpp

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 前序遍历
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";   // ① 访问根
    preorder(root->left);        // ② 遍历左子树
    preorder(root->right);       // ③ 遍历右子树
}

// 中序遍历
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);         // ① 遍历左子树
    cout << root->val << " ";   // ② 访问根
    inorder(root->right);        // ③ 遍历右子树
}

// 后序遍历
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);       // ① 遍历左子树
    postorder(root->right);      // ② 遍历右子树
    cout << root->val << " ";   // ③ 访问根
}

📌 三种遍历的应用场景

遍历方式	典型应用
前序遍历	复制一棵树、序列化/反序列化二叉树、表达式前缀表示
中序遍历	BST（二叉搜索树）的中序遍历结果是有序序列——高频考点！
后序遍历	计算目录大小（先算子目录再算父目录）、表达式后缀表示、释放树内存

🌊 层序遍历（BFS 实现）

层序遍历就是 BFS 在二叉树上的直接应用——用队列逐层输出：

cpp

void levelOrder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();  // 当前层的节点数
        for (int i = 0; i < size; i++) {
            TreeNode* cur = q.front();
            q.pop();
            cout << cur->val << " ";
            if (cur->left)  q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        cout << endl;  // 每层结束后换行
    }
}

⚠️ 易错点：层序遍历中 int size = q.size() 必须在 for 循环之前获取，不能在 for 的条件里写 i < q.size()——因为队列大小在循环中不断变化！

🔨 根据遍历序列重建二叉树

这是 GESP 六级的高频题型，核心结论：

前序 + 中序 → 唯一确定一棵树 ✅后序 + 中序 → 唯一确定一棵树 ✅前序 + 后序 → 不能唯一确定 ❌

重建原理（前序 + 中序）：

前序遍历：[根 | 左子树 | 右子树]
中序遍历：[左子树 | 根 | 右子树]

前序的第一个元素是根节点
在中序中找到根节点，左边是左子树、右边是右子树
递归构建左右子树

cpp

TreeNode* build(vector<int>& preorder, vector<int>& inorder,
                int preL, int preR, int inL, int inR) {
    if (preL > preR) return nullptr;

    int rootVal = preorder[preL];          // 前序首元素 = 根
    int rootIdx = inL;
    while (inorder[rootIdx] != rootVal)    // 在中序中找根
        rootIdx++;

    int leftSize = rootIdx - inL;          // 左子树大小

    TreeNode* root = new TreeNode(rootVal);
    root->left  = build(preorder, inorder, preL + 1, preL + leftSize, inL, rootIdx - 1);
    root->right = build(preorder, inorder, preL + leftSize + 1, preR, rootIdx + 1, inR);
    return root;
}

五、DFS vs BFS 选择策略表

考试中的决策口诀：求最短/最少 → BFS；求所有方案/判断连通 → DFS

题目特征	推荐算法	原因
求最少步数 / 最短路径	BFS	BFS 层序扩展，第一次到达即最短
求所有方案 / 全排列 / 组合枚举	DFS	天然适合暴力枚举所有可能
判断两点是否连通	DFS 或 BFS 均可	只需判断连通性，无最优性要求
迷宫求一条可行路径	DFS	找到一条路径即可
迷宫求最短路径	BFS	保证第一次到达终点是最短路径
二叉树按层输出	BFS（层序遍历）	队列天然支持逐层处理
连通块计数	DFS 或 BFS 均可	遍历标记即可
带权图最短路径	Dijkstra（📚 拓展 · 超纲）	BFS 只适用于无权图

📚 拓展 · 超纲：带权图最短路（Dijkstra）不在六级考纲内。六级只要求用 BFS 求无权图 / 网格迷宫的最少步数。 | 棋盘/网格路径搜索 | DFS + 回溯 | 需要尝试所有路径、回溯试探 |

六、实战技巧

🎯 技巧 1：visited 数组的正确使用

cpp

// ✅ 正确写法：入队/递归前标记
visited[nxt] = true;
q.push(nxt);

// ❌ 错误写法：出队时才标记（会导致大量重复入队 → TLE）
int cur = q.front(); q.pop();
visited[cur] = true;  // 太晚了！

原则：一旦发现某个状态，立即标记，不要等到处理时才标记。

🎯 技巧 2：方向数组 dx/dy

网格类问题中，用方向数组代替冗长的 if-else：

cpp

// 四方向：上、右、下、左
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

// 八方向（含对角线）
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 使用方式
for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
        // 合法，继续处理
    }
}

🎯 技巧 3：回溯标记与恢复

当需要在 DFS 中寻找所有路径或枚举所有方案时，需要在递归返回后恢复访问标记：

cpp

void dfs(int x, int y) {
    if (x == ex && y == ey) {
        ans++;  // 找到一条路径
        return;
    }
    visited[x][y] = true;    // 标记：这条路正在走

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (/* 合法 && 未访问 */) {
            dfs(nx, ny);
        }
    }

    visited[x][y] = false;   // 🔑 恢复标记：回溯，让其他路径可以经过这里
}

⚠️ 高频考点辨析：
求连通块/判断可达 → visited 标记后不恢复（每个节点只需访问一次）
求所有路径/排列组合 → visited 标记后要恢复（回溯，允许其他分支再次访问）

七、完整 C++ 代码模板汇总

模板 1：DFS 递归（网格迷宫求路径数）

cpp

#include <iostream>
#include <cstring>
using namespace std;

int n, m, ans = 0;
int grid[105][105];
bool visited[105][105];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void dfs(int x, int y) {
    if (x == n - 1 && y == m - 1) {
        ans++;
        return;
    }
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m
            && !visited[nx][ny] && grid[nx][ny] == 0) {
            dfs(nx, ny);
        }
    }
    visited[x][y] = false;  // 回溯恢复
}

int main() {
    // 输入 n, m 和网格（0=可走，1=障碍）
    memset(visited, false, sizeof(visited));
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}

模板 2：BFS（网格最短路径）

💻 编译器提示（C++17 语法）：模板中的 auto [x, y] = q.front(); 是 C++17 结构化绑定，用于把 pair<int,int> 一次性解包为 x、y。
GESP 考试环境（新版 g++）默认支持；
若你的 Dev-C++ 报 expected unqualified-id before '[' token 错误，说明编译器较旧（如 TDM-GCC 4.9.2），可改写为 C++11 等价形式： int x = q.front().first; int y = q.front().second; q.pop(); （本书后续 BFS 模板均采用结构化绑定写法，替换方法相同。）

cpp

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int n, m;
int grid[105][105];
int dist[105][105];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int bfs(int sx, int sy, int ex, int ey) {
    queue<pair<int, int>> q;
    memset(dist, -1, sizeof(dist));
    dist[sx][sy] = 0;
    q.push({sx, sy});

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        if (x == ex && y == ey) return dist[x][y];

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m
                && grid[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return -1;  // 不可达
}

int main() {
    // 输入 n, m 和网格
    cout << bfs(0, 0, n - 1, m - 1) << endl;
    return 0;
}

模板 3：二叉树层序遍历

cpp

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 层序遍历，按层输出
void levelOrder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* cur = q.front();
            q.pop();
            cout << cur->val << " ";
            if (cur->left)  q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        cout << endl;
    }
}

八、高频易错点与考试常见考法

🔴 易错点清单

#	易错点	正确做法
1	BFS 出队才标记 visited，导致重复入队 TLE	入队时立即标记
2	层序遍历 for 循环条件写 `i < q.size()`	循环前用变量保存 `size = q.size()`
3	DFS 求所有路径时忘记恢复 visited	递归返回后 `visited[x][y] = false`
4	非递归 DFS 中先出栈再标记 visited	入栈时立即标记
5	方向数组的坐标对应搞反（dx 对应行、dy 对应列）	牢记 `dx → 行变化`，`dy → 列变化`
6	BFS 求最短路径忘记检查障碍物	入队前同时检查 `dist == -1` 和 `grid == 0`

📝 考试常见考法

选择题：给定图和起点，要求写出 BFS/DFS 的节点访问序列
选择题：给定前序和中序遍历序列，要求写出后序遍历结果（或画出树的结构）
填空题：网格 BFS 求最短步数，补全代码中的关键行
编程题：迷宫求最短路径（BFS）或求所有路径数（DFS+回溯）
编程题：给定遍历序列重建二叉树，输出某种遍历结果

九、📝 实战练习

练习题 1（单选题）

题目： 一棵二叉树的前序遍历为 ABCDEFG，中序遍历为 CBDAFEG，则该二叉树的后序遍历结果为（）

A. CDBFGEA
B. CDBGFEA
C. CDGFBEA
D. GFEDCBA

🔑 点击查看答案与解析

答案： A

解析：

前序首元素 A 是根；中序中 A 左边 CBD 是左子树，右边 FEG 是右子树。
左子树：前序 BCD，中序 CBD → B 是根，C 是左孩子，D 是右孩子。
右子树：前序 FEG，中序 FEG → F 是根，E 是左孩子，G 是右孩子。
后序遍历（左-右-根）：C D B F G E A

        A
       / \
      B   E
     / \ / \
    C  D F  G

---

练习题 2（填空题）

题目： 以下 BFS 代码用于求 n×m 网格迷宫从 (0,0) 到 (n-1,m-1) 的最短步数（0=可走，1=障碍）。请补全划线处的代码：

cpp

int bfs() {
    queue<pair<int,int>> q;
    memset(dist, -1, sizeof(dist));
    dist[0][0] = 0;
    q.push({0, 0});
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        if (x == n-1 && y == m-1) return dist[x][y];
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m
                && grid[nx][ny] == 0 && ________) {  // 划线处
                dist[nx][ny] = ________;              // 划线处
                q.push({nx, ny});
            }
        }
    }
    return -1;
}

🔑 点击查看答案与解析

答案：

CPP

//第一空：
dist[nx][ny] == -1

//第二空
dist[x][y] + 1

解析：

dist[nx][ny] == -1 判断邻居是否尚未被访问过（初始值为 -1，赋值后 ≥ 0）。这是 BFS 中替代 visited 数组的常用写法。
dist[x][y] + 1 表示邻居的距离等于当前节点距离 +1。

练习题 3（判断题）

题目： 求无权图中两点之间的最短路径，DFS 比 BFS 更合适。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 正好说反了！

BFS 是按层扩散的，第一次到达终点时走的就是最短路径（因为所有边权重相同）
DFS 是一条路走到黑，找到的不一定是最短的，可能绕了远路

所以求最短路径应该用 BFS，而不是 DFS。

🍎 生活比喻：BFS 像水波纹——从起点一圈一圈往外扩，最先到达目标的那圈波纹，半径就是最短距离。DFS 像瞎走——可能绕了大弯才到。

---

练习题 4（单选题）

题目： 回溯法（Backtracking）的基本流程是？（）

A. 选择 → 递归 → 撤销
B. 递归 → 选择 → 撤销
C. 撤销 → 选择 → 递归
D. 选择 → 撤销 → 递归

🔑 点击查看答案与解析

答案： A

解析： 回溯法（DFS 的一种应用）的标准流程：

选择：做出一个选择（比如选某个元素加入路径）
递归：进入下一层，继续搜索
撤销：递归返回后，撤销刚才的选择（恢复现场），以便尝试其他选择

这就是经典的"选择-递归-撤销"三步曲。

选 A。

💡 典型例子：全排列问题。选一个数加入路径 → 递归排剩下的 → 把这个数从路径中移除（撤销），换下一个数试试。

---

练习题 5（单选题）

题目： BFS 广度优先搜索使用什么数据结构来存储待访问的节点？（）

A. 栈
B. 队列
C. 数组
D. 链表

🔑 点击查看答案与解析

答案： B

解析： BFS 按层扩散，先访问的节点的邻居也要先被处理——这正好是队列的"先进先出"（FIFO）特性。

基本步骤：

起点入队
出队一个节点，处理它
把它的所有未访问邻居入队
重复 2-3 直到队列为空

选 B。

💡 对比记忆：
DFS → 栈（或递归）→ 先进后出 → 一条路走到黑
BFS → 队列 → 先进先出 → 层序扩散

---

练习题 6（判断题）

题目： 用 BFS 求迷宫最短路径时，距离数组 dist 的初始值应该设为 -1（表示未访问），起点的 dist 设为 0。（）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： 这是 BFS 求最短路径的标准做法：

dist 数组初始化为 -1（表示未访问/不可达）
起点 dist[start] = 0
对于当前节点 x 的邻居 nx：如果 dist[nx] == -1，则 dist[nx] = dist[x] + 1，并将 nx 入队

这样 dist[终点] 就是起点到终点的最短距离。

🔥 高频考点：dist 数组既是距离数组，又起到 visited 数组的作用——值为 -1 就是没访问过，值 ≥ 0 就是已访问过且距离已知。

---

练习题 7（单选题）

题目： 在二维网格 DFS/BFS 中，常用方向数组表示上下左右四个方向。下列哪个是正确的方向数组定义？（）

A. int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0};
B. int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1};
C. int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0};
D. 以上都正确

🔑 点击查看答案与解析

答案： D

解析： 方向数组只要能正确表示四个方向就行，顺序无所谓。上下左右四个方向的坐标变化：

上：(-1, 0)
下：(1, 0)
左：(0, -1)
右：(0, 1)

A、B、C 都包含了这四个方向，只是顺序不同，所以都正确。

选 D。

💡 注意：题目中要确认行号用 x 还是 y，列号用什么。一般约定 dx 是行的变化，dy 是列的变化。

---

练习题 8（编程题）

题目： 给定一个 n × m 的迷宫，0 表示通路，1 表示墙壁。从左上角 (0,0) 出发，能不能走到右下角 (n-1, m-1)？请用 DFS 实现。

输入：第一行 n 和 m，接下来 n 行每行 m 个 0/1
输出：能到达输出 "Yes"，否则输出 "No"

样例输入：

样例输出：

Yes

🔑 点击查看答案与解析

答案：

cpp

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<vector<int>> maze;
vector<vector<bool>> visited;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool dfs(int x, int y) {
    // 到达终点
    if (x == n-1 && y == m-1) return true;
    
    visited[x][y] = true;  // 标记已访问
    
    // 尝试四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        // 边界判断 + 通路 + 未访问
        if (nx >= 0 && nx < n && ny >= 0 && ny < m 
            && maze[nx][ny] == 0 && !visited[nx][ny]) {
            if (dfs(nx, ny)) return true;  // 找到就直接返回
        }
    }
    return false;  // 四个方向都走不通
}

int main() {
    cin >> n >> m;
    maze.resize(n, vector<int>(m));
    visited.resize(n, vector<bool>(m, false));
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> maze[i][j];
    
    if (dfs(0, 0)) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

解析： DFS 迷宫问题模板：

边界判断：不能走出地图
条件判断：是通路 + 没访问过
标记访问：防止走回头路
四个方向递归：上下左右各试一次
找到就返回：只要一个方向成功就成功

💡 注意：这是"能否到达"问题，DFS 和 BFS 都可以。但如果要求最短路径，必须用 BFS。

---

十、📊 考点总结表

考点	重要程度	出题形式	易错点
DFS 核心思想	⭐⭐⭐⭐⭐	选择/判断	深度优先，一条路走到黑
DFS 实现（递归/栈）	⭐⭐⭐⭐⭐	代码填空/编程	递归终止条件
BFS 核心思想	⭐⭐⭐⭐⭐	选择/判断	层序扩散，先近后远
BFS 实现（队列）	⭐⭐⭐⭐⭐	代码填空/编程	入队出队顺序
DFS vs BFS 对比	⭐⭐⭐⭐⭐	选择/判断	最短路径用BFS
回溯法三步曲	⭐⭐⭐⭐	选择/编程	选择→递归→撤销
visited 标记访问	⭐⭐⭐⭐⭐	代码填空	忘记标记导致死循环
方向数组 dx/dy	⭐⭐⭐⭐	代码填空	边界判断不能少
最短路径（BFS）	⭐⭐⭐⭐⭐	编程题	dist数组初始化-1
迷宫问题	⭐⭐⭐⭐⭐	编程题	边界 + 通路 + 未访问
二叉树 DFS 遍历	⭐⭐⭐⭐	选择/程序阅读	前中后序
二叉树 BFS 层序	⭐⭐⭐⭐	选择/程序阅读	队列实现

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│        DFS/BFS · 必背速记卡                 │
├─────────────────────────────────────────────┤
│  1. DFS：深度优先，一条路走到黑，碰壁回头   │
│  2. DFS用栈（或递归），先进后出             │
│  3. BFS：广度优先，层序扩散，先近后远       │
│  4. BFS用队列，先进先出                     │
│  5. 最短路径（无权图）→ BFS                 │
│  6. 所有路径/方案数 → DFS（回溯）           │
│  7. 回溯三步曲：选择 → 递归 → 撤销         │
│  8. visited数组：标记已访问，防止重复走     │
│  9. 方向数组：上下左右，dx[4], dy[4]       │
│ 10. BFS距离数组：初始-1，起点设0            │
│ 11. dist[nx] = dist[x] + 1                 │
│ 12. DFS空间：O(深度)，BFS空间：O(节点数)   │
│ 13. 迷宫四判断：边界、通路、未访问、目标    │
│ 14. 二叉树前中后序：DFS；层序遍历：BFS     │
│ 15. 写搜索：先想状态怎么表示，再想怎么转移  │
└─────────────────────────────────────────────┘

第4章 搜索算法 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、DFS 深度优先搜索 ​

🔍 核心思想 ​

🎨 生活类比 ​

📐 算法流程 ​

🧩 递归实现模板（最常用） ​

🧩 栈实现模板（非递归） ​

📌 应用场景 ​

✂️ 剪枝思想 ​

二、BFS 广度优先搜索 ​

🔍 核心思想 ​

🎨 生活类比 ​

📐 算法流程 ​

🧩 队列实现模板 ​

📌 应用场景 ​

💡 BFS 的关键性质 ​

三、DFS vs BFS 对比 ​

四、二叉树的搜索算法 ​

🌲 三种深度遍历 ​

🧩 代码实现 ​

📌 三种遍历的应用场景 ​

🌊 层序遍历（BFS 实现） ​

🔨 根据遍历序列重建二叉树 ​

五、DFS vs BFS 选择策略表 ​

六、实战技巧 ​

🎯 技巧 1：visited 数组的正确使用 ​

🎯 技巧 2：方向数组 dx/dy ​

🎯 技巧 3：回溯标记与恢复 ​

七、完整 C++ 代码模板汇总 ​

模板 1：DFS 递归（网格迷宫求路径数） ​

模板 2：BFS（网格最短路径） ​

模板 3：二叉树层序遍历 ​

八、高频易错点与考试常见考法 ​

🔴 易错点清单 ​

📝 考试常见考法 ​

九、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（填空题） ​

练习题 3（判断题） ​

练习题 4（单选题） ​

练习题 5（单选题） ​

练习题 6（判断题） ​

练习题 7（单选题） ​

练习题 8（编程题） ​

十、📊 考点总结表 ​

⭐ 必背速记卡 ​

第4章搜索算法

🎯 本章学习目标

🗺️ 本章知识图谱

一、DFS 深度优先搜索

🔍 核心思想

🎨 生活类比

📐 算法流程

🧩 递归实现模板（最常用）

🧩 栈实现模板（非递归）

📌 应用场景

✂️ 剪枝思想

二、BFS 广度优先搜索

🔍 核心思想

🎨 生活类比

📐 算法流程

🧩 队列实现模板

📌 应用场景

💡 BFS 的关键性质

三、DFS vs BFS 对比

四、二叉树的搜索算法

🌲 三种深度遍历

🧩 代码实现

📌 三种遍历的应用场景

🌊 层序遍历（BFS 实现）

🔨 根据遍历序列重建二叉树

五、DFS vs BFS 选择策略表

六、实战技巧

🎯 技巧 1：visited 数组的正确使用

🎯 技巧 2：方向数组 dx/dy

🎯 技巧 3：回溯标记与恢复

七、完整 C++ 代码模板汇总

模板 1：DFS 递归（网格迷宫求路径数）

模板 2：BFS（网格最短路径）

模板 3：二叉树层序遍历

八、高频易错点与考试常见考法

🔴 易错点清单

📝 考试常见考法

九、📝 实战练习

练习题 1（单选题）

练习题 2（填空题）

练习题 3（判断题）

练习题 4（单选题）

练习题 5（单选题）

练习题 6（判断题）

练习题 7（单选题）

练习题 8（编程题）

十、📊 考点总结表

⭐ 必背速记卡