DFS（深度优先搜索）和 BFS（广度优先搜索）是新手必掌握的基础

本文用9道经典洛谷题，把 DFS、BFS 讲得明明白白，纯新手也能直接看懂

一、先搞懂：什么是 DFS？

DFS = 深度优先搜索 一句话：一条路走到黑，不撞南墙不回头，回头了再换条路走。 几乎都用递归实现，核心是递归 + 回溯。

DFS 万能模板（新手背会就能用）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void dfs(当前状态) {
    // 1. 终止条件：到头了/满足要求了，直接返回
    if(满足终止条件) {
        记录答案/判断结果;
        return;
    }
    // 2. 遍历所有可能的分支
    for(所有可选方向/选择) {
        标记选择;       // 选这个
        dfs(下一个状态); // 往下走
        取消标记;       // 回溯：不选这个，换一个
    }
}

二、DFS 四大题型（9道题全涵盖）

结合所有题目，我们分成4类，新手按这个分类学最快，全覆盖所有搜索场景！

题型1：组合/排列枚举类 DFS（选/不选、填充枚举）

适用场景：从一堆东西里选若干个、填充通配符、枚举排列组合、判断合法组合。 核心：要么选/不选，要么固定顺序枚举，回溯保证不重不漏。

对应题目

1. P2036 PERKET：配料选或不选，求酸度苦度最小差值
2. P1036 选数：从n个数选k个，求和为质数的数量
3. P9241 飞机降落：枚举飞机降落顺序，判断能否全降落
4. B4158 质数补全：把*填0-9，找最小质数

题型2：记忆化 DFS（递归优化神器）

适用场景：纯递归会重复计算无数次，效率极低，用数组存已算结果。 核心：memo[状态]存结果，算过直接返回，空间换时间。

对应题目

P1464 Function：递归函数优化

• 原始递归重复计算爆炸，记忆化后秒出答案

题型3：网格搜索 DFS（二维图遍历）

适用场景：二维矩阵/方格，上下左右/8方向搜索、填色、匹配单词。 核心：方向数组dx[]/dy[]，标记访问位置，边界判断。

对应题目

1. P1162 填涂颜色：把闭合圈内的0填2
2. P1101 单词方阵：找yizhong并标记

题型4：棋盘状态枚举 DFS（进阶网格）

适用场景：棋盘逐格放置棋子/状态，带胜负/终止条件，统计合法方案数。 核心：逐格遍历枚举状态，提前剪枝（不合法直接返回），回溯维护棋盘状态。

对应题目

P10386 五子棋对弈

• 5x5棋盘枚举白棋/黑棋，出现五子连珠平局立刻剪枝
• 统计白棋数量为13的合法方案数
• 逐格递归（x,y），切换状态后回溯，完美适配DFS模板

三、再搞懂：什么是 BFS？

BFS = 广度优先搜索 一句话：一层一层往外搜，先搜到的就是最短路径。 用队列实现，最适合求最短步数/最少操作次数。

BFS 万能模板（新手背会）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

queue<状态> q;
初始化起点，入队，标记访问;
while(!q.empty()) {
    取出队首;
    遍历所有邻点;
    if(邻点合法 && 没访问) {
       标记访问;
        记录步数;
        入队;
        if(到达终点) 直接返回结果;
    }
}

四、BFS 核心题型：最短路径

对应题目

P1135 奇怪的电梯：求从A到B最少按几次按钮

• 每层楼是节点，上下楼是边，BFS天生求最短路径
• 第一次到达终点就是最少步数，无需继续搜索

五、新手必记：DFS vs BFS 对比

搜索是算法的基础中的基础 搜索算法是最核心、最常用的算法，DFS 和 BFS 都是搜索算法的代表。