算法基础篇：（十七）深度优先搜索 DFS 实战指南：从选数到数独，手把手带你攻克DFS经典问题

前言

在算法世界里，深度优先搜索（DFS）就像一位 “执着的探险家”—— 一旦选择了一条路径，就会义无反顾地走到尽头，遇到死胡同再掉头寻找新的可能。这种 “不撞南墙不回头” 的特性，让 DFS 在枚举、组合、路径规划等问题中大放异彩。 今天这篇文章，我们不搞空洞的理论说教，而是以 “问题驱动” 的方式，逐个拆解这些经典例题。从 “选数求和判素数” 到 “飞机降落调度”，再到 “八皇后”“数独”，每道题都会讲清 “为什么用 DFS”“递归函数怎么设计”“如何剪枝提速”，并附上可直接运行的 C++ 代码。无论你是刚接触 DFS 的新手，还是想巩固实战能力的老手，都能从这篇文章中找到收获。下面就让我们正式开始吧！

一、热身题：选数问题（洛谷 P1036）——DFS 与素数判断的结合

1.1 题目描述：从 n 个数中选 k 个，求和为素数的方案数

题目是这样的：已知 n 个整数和一个整数 k（k < n），从这 n 个整数中任选 k 个相加，计算和为素数的方案有多少种。比如输入4 3和3 7 12 19，所有组合的和分别是 3+7+12=22（非素数）、3+7+19=29（素数）、3+12+19=34（非素数）、7+12+19=38（非素数），所以答案是 1。

题目链接如下：https://www.luogu.com.cn/problem/P1036

这道题看似简单，却包含了 DFS 的核心思想：组合型枚举—— 因为选数的顺序不影响结果（比如选 3、7、19 和选 7、3、19 是同一种方案），所以需要控制选数的顺序，避免重复枚举。

1.2 思路分析：如何用 DFS 实现组合型枚举？

（1）问题拆解：选数的 “决策树”

我们可以把选数过程想象成一棵 “决策树”：每一层代表 “选第几个数”，每个分支代表 “选哪个数”。比如 n=4、k=3 时，第一层选第一个数（只能从 1 开始），第二层选第二个数（只能从第一层选的数的下一个开始），第三层选第三个数（同理）。这样就能保证选出来的数是递增的，避免重复。

（2）递归函数设计：两个关键参数

递归函数需要两个核心参数：

• pos：当前要选第几个数（比如 pos=1 表示选第一个数，pos=k 时表示已经选够 k 个，需要判断和是否为素数）；
• begin：当前选数的起始位置（比如上一个数选了 i，这次就从 i+1 开始，保证组合不重复）；
• 额外用一个全局变量path记录当前选中数的和（避免用数组存储再求和，提高效率），ret记录符合条件的方案数。

（3）素数判断：试除法的优化

判断一个数是否为素数，最常用的是 “试除法”：从 2 到√x 遍历，如果 x 能被其中任何一个数整除，就不是素数。这里要注意两个边界：x≤1 时不是素数，x=2 时是素数。

1.3 完整代码与注释

#include <iostream>
using namespace std;

const int N = 25;  // 题目中n≤20，开25足够
int n, k;
int a[N];          // 存储输入的n个整数
int ret = 0;       // 记录符合条件的方案数
int path_sum = 0;  // 记录当前选中数的和（path_sum比path更直观）

// 试除法判断素数
bool is_prime(int x) {
    if (x <= 1) return false;  // 1及以下不是素数
    // 优化：只需要遍历到√x，因为如果x有因子，必然有一个≤√x
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) return false;  // 能整除，不是素数
    }
    return true;
}

// DFS函数：pos-当前要选第几个数，begin-选数的起始位置
void dfs(int pos, int begin) {
    // 递归终止条件：选够k个数了
    if (pos > k) {
        if (is_prime(path_sum)) {  // 判断和是否为素数
            ret++;
        }
        return;
    }

    // 枚举选数：从begin开始，避免重复
    for (int i = begin; i <= n; i++) {
        // 选择当前数：累加和
        path_sum += a[i];
        // 递归：选下一个数（pos+1），下一次从i+1开始选
        dfs(pos + 1, i + 1);
        // 回溯：撤销选择，恢复现场
        path_sum -= a[i];
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {  // 数组从1开始，方便理解
        cin >> a[i];
    }
    dfs(1, 1);  // 从选第1个数开始，起始位置是1
    cout << ret << endl;
    return 0;
}

1.4 关键技巧：为什么要 “恢复现场”？

在 DFS 中，“恢复现场”（比如path_sum -= a[i]）是核心操作之一。因为递归函数会多次调用，而path_sum是全局变量 —— 如果不恢复，下一次枚举其他分支时，会带着上一个分支的结果，导致计算错误。

比如选第一个数时，我们加了 a [1]，递归处理完所有包含 a [1] 的分支后，必须减去 a [1]，才能再去处理包含 a [2] 的分支。这就像探险家走完一条路后，要回到起点再走另一条路，不能带着上一条路的 “行李”。

二、进阶题：飞机降落（洛谷 P9241）——DFS 与全排列剪枝

2.1 题目回顾：调度飞机降落，判断是否全部安全

机场只有一条跑道，N 架飞机要降落。每架飞机有三个参数：T_i（到达时间）、D_i（最大盘旋时间，即最晚降落时间为T_i+D_i）、L_i（降落所需时间）。要求判断是否存在一种降落顺序，让所有飞机都能安全降落（前一架降落后，后一架才能开始降）。

题目链接如下：https://www.luogu.com.cn/problem/P9241

2.2 思路分析：为什么用 DFS 枚举全排列？

因为飞机的降落顺序是 “排列问题”—— 不同的顺序会导致不同的结果，所以需要枚举所有可能的排列，判断是否存在一种排列让所有飞机都能安全降落。

但 N 的范围是≤10，如果直接枚举全排列，10! = 3628800，这个数量级是可以接受的（1000 万以内的运算，C++ 能轻松处理）。但如果不剪枝，可能会做很多无用功，所以需要加入剪枝优化。

（1）递归函数设计：两个关键参数

• pos：当前要安排第几个飞机（pos=1 表示安排第一个，pos=N+1 表示所有飞机都安排完，返回 true）；
• end_time：上一架飞机降落结束的时间（当前飞机的最早开始时间是 end_time，同时不能晚于当前飞机的 T_i+D_i）；
• 额外用一个st数组标记哪些飞机已经被安排过（避免重复安排）。

（2）剪枝优化：减少无用枚举

• 剪枝 1：如果当前飞机已经被安排过（st[i] = true），直接跳过；
• 剪枝 2：如果当前飞机的最晚开始时间（T_i+D_i） < end_time，说明即使现在安排这架飞机，也无法在最晚时间前开始，直接跳过；
• 剪枝 3：如果已经找到一种合法的排列，直接返回 true，不需要再枚举其他排列（递归函数返回 bool 类型，找到合法解就立即终止）。

2.3 完整代码与注释

#include <iostream>
#include <cstring>  // 用于memset
using namespace std;

const int N = 15;  // N≤10，开15足够
int n;              // 飞机数量
int T[N], D[N], L[N];  // 每架飞机的T_i、D_i、L_i
bool st[N];         // 标记飞机是否已被安排（true表示已安排）

// DFS函数：pos-当前安排第几个飞机，end_time-上一架结束时间
// 返回值：是否存在合法的安排方式
bool dfs(int pos, int end_time) {
    // 递归终止条件：所有飞机都安排完了
    if (pos > n) {
        return true;
    }

    // 枚举每一架飞机，尝试安排
    for (int i = 1; i <= n; i++) {
        // 剪枝1：飞机已经安排过，跳过
        if (st[i]) continue;
        // 剪枝2：当前飞机的最晚开始时间 < 上一架结束时间，无法安排，跳过
        if (end_time > T[i] + D[i]) continue;

        // 选择当前飞机：标记为已安排
        st[i] = true;
        // 计算当前飞机的结束时间：最早开始时间是max(end_time, T[i])，加上降落时间L[i]
        int new_end = max(end_time, T[i]) + L[i];
        // 递归安排下一架飞机，如果找到合法解，直接返回true
        if (dfs(pos + 1, new_end)) {
            return true;
        }
        // 回溯：撤销选择，恢复现场
        st[i] = false;
    }

    // 枚举完所有飞机，都没有合法解，返回false
    return false;
}

int main() {
    int T_case;  // 测试数据组数
    cin >> T_case;
    while (T_case--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> T[i] >> D[i] >> L[i];
        }
        // 每次处理一组数据前，清空st数组（0表示未安排）
        memset(st, 0, sizeof st);
        // 从安排第1架飞机开始，上一架结束时间是0（初始状态，没有飞机降落过）
        if (dfs(1, 0)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

2.4 关键技巧：剪枝的重要性

如果不剪枝，枚举 10 架飞机的全排列需要 10! = 3628800 次递归，虽然能运行，但加上剪枝后，很多无效的分支会被直接跳过，运行速度会快很多。比如当end_time已经超过某架飞机的最晚开始时间时，就不需要再递归处理这架飞机的后续分支了，直接跳过，节省了大量时间。

另外，递归函数返回 bool 类型，一旦找到合法解就立即返回，避免了不必要的枚举 —— 这也是一种重要的剪枝策略（“最优性剪枝” 的变种，这里是 “存在性剪枝”）。

三、经典题：八皇后问题（洛谷 P1219）——DFS 与冲突检测

3.1 题目回顾：n×n 棋盘放 n 个皇后，无冲突

八皇后问题是 DFS 的经典应用：在 n×n 的棋盘上放置 n 个皇后，使得每行、每列、每条对角线上都只有一个皇后。要求按字典序输出前 3 个解，并统计解的总数。

比如 n=6 时，其中一个解是 “2 4 6 1 3 5”，表示第 1 行的皇后在第 2 列，第 2 行在第 4 列，以此类推。

题目链接如下：https://www.luogu.com.cn/problem/P1219

3.2 思路分析：如何避免冲突？

八皇后问题的核心是 “冲突检测”—— 放置一个皇后后，要确保它所在的行、列、对角线没有其他皇后。由于我们是 “一行一行” 放置皇后（每一行放一个），所以行冲突已经天然避免了，只需要检测列和对角线冲突。

（1）冲突检测的三个维度

• 列冲突：某一列是否已经有皇后（用col数组标记，col[j] = true表示第 j 列有皇后）；
• 主对角线冲突：主对角线是指从左上到右下的对角线，其特点是 “行号 - 列号” 为定值（比如 (1,2)、(2,3)、(3,4) 的行号 - 列号都是 - 1）。为了避免负数，我们可以加上 n，得到j - i + n（比如 n=6 时，-1+6=5，范围是 1~2n-1），用st1数组标记；
• 副对角线冲突：副对角线是指从右上到左下的对角线，其特点是 “行号 + 列号” 为定值（比如 (1,4)、(2,3)、(3,2) 的行号 + 列号都是 5），用st2数组标记。

（2）递归函数设计：按行放置

递归函数的参数是x（当前要放置皇后的行号），因为每行只放一个，所以 x 从 1 到 n 遍历：

• 当 x > n 时，说明所有皇后都放置完毕，统计解的数量，如果是前 3 个解，就输出；
• 对于当前行 x，枚举每一列 y，判断 y 列、主对角线、副对角线是否有冲突：
  • 如果没有冲突，标记冲突状态，记录当前列 y（用path数组存储），递归处理下一行 x+1；
  • 回溯：撤销冲突标记，删除path数组中的当前列 y。

3.3 完整代码与注释

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

const int N = 15;  // n≤13，开15足够
int n;              // 棋盘大小n×n
// 冲突标记数组：col[j]-第j列是否有皇后，st1-主对角线，st2-副对角线
bool col[N], st1[N * 2], st2[N * 2];
int ret = 0;        // 解的总数
vector<int> path;   // 存储当前解：path[i]表示第i+1行的皇后列号

// DFS函数：x-当前要放置皇后的行号
void dfs(int x) {
    // 递归终止条件：所有行都放置了皇后
    if (x > n) {
        ret++;  // 解的数量加1
        // 如果是前3个解，输出
        if (ret <= 3) {
            for (int i = 0; i < path.size(); i++) {
                cout << path[i] << " ";
            }
            cout << endl;
        }
        return;
    }

    // 枚举当前行的每一列y，尝试放置皇后
    for (int y = 1; y <= n; y++) {
        // 检测冲突：列y、主对角线(y-x+n)、副对角线(y+x)是否有皇后
        if (col[y] || st1[y - x + n] || st2[y + x]) {
            continue;  // 有冲突，跳过
        }

        // 选择当前列y：标记冲突，记录路径
        col[y] = true;
        st1[y - x + n] = true;
        st2[y + x] = true;
        path.push_back(y);

        // 递归处理下一行
        dfs(x + 1);

        // 回溯：撤销选择，恢复现场
        path.pop_back();
        st2[y + x] = false;
        st1[y - x + n] = false;
        col[y] = false;
    }
}

int main() {
    cin >> n;
    dfs(1);  // 从第1行开始放置皇后
    cout << ret << endl;  // 输出解的总数
    return 0;
}

3.4 关键技巧：对角线冲突的标记方法

主对角线和副对角线的标记是八皇后问题的难点，也是重点。记住这两个规律：

• 主对角线（左上→右下）：行号 - 列号 = 常数，加上 n 后可以将范围映射到 1~2n-1，避免负数；
• 副对角线（右上→左下）：行号 + 列号 = 常数，范围是 2~2n（行号和列号都从 1 开始）。

比如 n=6 时，第 1 行第 2 列的皇后：

• 主对角线标记：2 - 1 + 6 = 7；
• 副对角线标记：2 + 1 = 3；如果下一行（第 2 行）想放第 3 列，主对角线标记是 3 - 2 + 6 = 7，和之前的 7 重复，说明有冲突，不能放。

这种标记方法是高效且直观的，避免了用二维数组遍历检测冲突，大大提高了效率。

四、挑战题：数独（洛谷 P1784）——DFS 与多维度冲突检测

4.1 题目回顾：填充 9×9 数独，满足行、列、3×3 宫不重复

数独是大家熟悉的游戏：9×9 的棋盘，部分格子有数字（1~9），要求填充剩余格子，使得每一行、每一列、每一个 3×3 的粗线宫内的数字都不重复，且每个数字都是 1~9。题目保证有唯一解。

比如输入：

800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400

输出是填充完整的数独矩阵。

题目链接如下：https://www.luogu.com.cn/problem/P1784

4.2 思路分析：如何高效填充与检测冲突？

数独的难点在于 “多维度冲突检测”（行、列、3×3 宫）和 “搜索顺序优化”（如果盲目枚举，效率会很低）。

（1）冲突检测的三个维度

• 行冲突：row[i][num] = true表示第 i 行已经有数字 num；
• 列冲突：col[j][num] = true表示第 j 列已经有数字 num；
• 3×3 宫冲突：st[x][y][num] = true表示第 (x,y) 个 3×3 宫已经有数字 num（x 是宫的行号，0~2；y 是宫的列号，0~2）。如何确定某个格子 (i,j) 属于哪个宫？x = i / 3，y = j / 3（i 和 j 从 0 开始）。

比如格子 (4,5)（第 5 行第 6 列，从 0 开始）：

• 宫的行号 x = 4 / 3 = 1（0~2）；
• 宫的列号 y = 5 / 3 = 1（0~2）；所以属于第 (1,1) 个宫。

（2）递归函数设计：按格子顺序填充

递归函数的参数是i和j（当前要填充的格子的行号和列号）：

• 如果 j == 9（当前行填完了），就换行填下一行（i+1，j=0）；
• 如果 i == 9（所有格子都填完了），返回 true（找到唯一解）；
• 如果当前格子已经有数字（a [i][j] != 0），直接递归处理下一个格子（i, j+1）；
• 如果当前格子是空的（a [i][j] == 0），枚举 1~9 的数字，判断是否有冲突：
  • 没有冲突：标记冲突状态，填充数字，递归处理下一个格子；
  • 回溯：撤销冲突标记，清空数字；
  • 找到唯一解后，立即返回 true，避免多余枚举。

（3）搜索顺序优化：为什么按行按列依次填充？

数独的搜索顺序很重要，如果盲目枚举，可能会做很多无用功。按 “行优先” 的顺序填充（从左到右，从上到下），可以尽早发现冲突，减少递归深度。比如如果某个格子必须填 5，而前面的格子已经把 5 用了，就可以提前剪枝。

4.3 完整代码与注释

#include <iostream>
using namespace std;

const int N = 10;  // 数独是9×9，数组从0开始，开10足够
int a[N][N];        // 存储数独矩阵
// 冲突标记数组：row[i][num]-第i行有num，col[j][num]-第j列有num，st[x][y][num]-第(x,y)宫有num
bool row[N][N], col[N][N], st[N][N][N];

// DFS函数：i-当前格子行号，j-当前格子列号
bool dfs(int i, int j) {
    // 换行处理：当前行填完了，填下一行的第0列
    if (j == 9) {
        i++;
        j = 0;
    }
    // 递归终止条件：所有格子都填完了（找到唯一解）
    if (i == 9) {
        return true;
    }
    // 当前格子已有数字，直接处理下一个格子
    if (a[i][j] != 0) {
        return dfs(i, j + 1);
    }

    // 枚举1~9的数字，尝试填充当前格子
    for (int num = 1; num <= 9; num++) {
        // 计算当前格子所属的3×3宫的坐标（x-宫行号，y-宫列号）
        int x = i / 3, y = j / 3;
        // 检测冲突：行、列、宫是否已有该数字
        if (row[i][num] || col[j][num] || st[x][y][num]) {
            continue;  // 有冲突，跳过
        }

        // 选择当前数字：标记冲突，填充格子
        row[i][num] = true;
        col[j][num] = true;
        st[x][y][num] = true;
        a[i][j] = num;

        // 递归处理下一个格子，如果找到解，立即返回true
        if (dfs(i, j + 1)) {
            return true;
        }

        // 回溯：撤销选择，恢复现场
        a[i][j] = 0;
        st[x][y][num] = false;
        col[j][num] = false;
        row[i][num] = false;
    }

    // 枚举完所有数字都无法填充，返回false
    return false;
}

int main() {
    // 输入数独矩阵（0表示空格子）
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> a[i][j];
            int num = a[i][j];
            if (num != 0) {
                // 标记已有数字的冲突状态
                row[i][num] = true;
                col[j][num] = true;
                int x = i / 3, y = j / 3;
                st[x][y][num] = true;
            }
        }
    }

    // 从第0行第0列开始填充
    dfs(0, 0);

    // 输出填充后的数独矩阵
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

4.4 关键技巧：如何处理输入与初始化？

数独的输入是 9 行字符串，每个字符是数字（0~9）。在输入时，我们需要同时初始化冲突标记数组：对于非 0 的数字，要标记它所在的行、列、宫已经有该数字，避免后续填充时冲突。

比如输入第 0 行是 “800000000”，那么 a [0][0] = 8，我们需要标记：

• row [0][8] = true（第 0 行有 8）；
• col [0][8] = true（第 0 列有 8）；
• 宫的坐标 x = 0/3 = 0，y = 0/3 = 0，所以 st [0][0][8] = true（第 (0,0) 宫有 8）。

这样，在后续填充时，就不会在第 0 行、第 0 列、第 (0,0) 宫再填 8 了。

五、DFS 实战总结：三大核心与四大技巧

通过以上 5 道题（选数、飞机降落、八皇后、数独，还有之前的枚举子集、组合、排列），我们可以总结出 DFS 的核心思想和实战技巧：

5.1 DFS 的三大核心

1. 递归设计：明确递归的 “终止条件” 和 “当前层要做的事”。比如选数问题的终止条件是选够 k 个数，当前层要做的是枚举选哪个数；八皇后问题的终止条件是填完 n 行，当前层要做的是枚举当前行的列号。
2. 状态恢复（回溯）：递归调用后，必须撤销当前层的选择，恢复到调用前的状态。比如选数问题中的path_sum -= a[i]，飞机降落问题中的st[i] = false，都是为了让下一次枚举不受当前层选择的影响。
3. 冲突检测 / 剪枝：这是 DFS 效率的关键。冲突检测（如八皇后的列和对角线检测）可以避免无效的递归；剪枝（如飞机降落的 “最晚开始时间” 剪枝）可以减少无用的分支，让程序更快运行。

5.2 DFS 的四大实战技巧

1. 组合型枚举用 “begin” 参数：避免重复枚举（如选数问题中，每次从 begin 开始选，保证组合递增）；
2. 排列型枚举用 “st” 数组：标记已选元素（如飞机降落问题中，标记已安排的飞机）；
3. 冲突检测用专用数组：避免二维遍历（如八皇后的 col、st1、st2 数组，数独的 row、col、st 数组）；
4. 递归函数返回 bool 类型：找到解后立即终止（如飞机降落、数独问题，找到合法解就返回 true，不需要再枚举）。

5.3 什么时候用 DFS？

当遇到以下类型的问题时，优先考虑 DFS：

• 枚举所有可能的方案（如子集、组合、排列）；
• 路径查找（如迷宫问题，虽然 BFS 更适合最短路，但 DFS 可以找所有路径）；
• 状态空间搜索（如八皇后、数独，每个状态是一个中间结果）；
• 需要回溯的问题（如选数、飞机降落，选择后需要撤销）。

总结

DFS 看似简单，但要真正用好，需要大量的实战练习。希望这篇文章能成为你 DFS 实战路上的 “垫脚石”，让你在算法竞赛或工程实践中，能轻松用 DFS 解决问题！