DFS 算法经典应用课堂笔记

---

📚 目录

1. DFS 基础回顾
2. 应用场景一：迷宫/网格寻路（带剪枝优化）
3. 应用场景二：组合数生成（从 n 个数中选 k 个）
4. 应用场景三：子集枚举（选或不选的决策）
5. 应用场景四：全排列生成
6. DFS 常见技巧总结

---

1. DFS 基础回顾

核心思想

• 深度优先搜索：一种通过递归尝试所有可能路径的搜索算法，“不撞南墙不回头”。
• 关键要素：
  • 状态：当前的位置、已选的元素、步数等。
  • 递归边界：满足目标条件或无法继续搜索时返回。
  • 回溯：撤销当前选择，尝试其他可能。

---

2. 应用场景一：迷宫/网格寻路（带剪枝优化）

问题描述

在一个 n×m 的网格中，从起点 r 走到终点 a，# 是障碍，x 是需要额外消耗 1 步的格子，求最短路径。

核心思路

• 遍历上下左右四个方向。
• 用 vis 数组标记已访问的格子，避免重复。
• 剪枝：如果当前步数已超过已知的最短路径，直接返回。

代码详解

#include<bits/stdc++.h>
using namespace std;

int n, m, ans = 1e9;  // ans 存储最短路径，初始化为极大值
int vis[30][30];       // 标记格子是否已访问
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};  // 四个方向的偏移量
int sx, sy, ex, ey;    // 起点 (sx,sy)，终点 (ex,ey)
char c[30][30];         // 存储网格

// 参数：当前坐标 (x,y)，已走步数 step
void dfs(int x, int y, int step){
    if(step > ans) return;  // 剪枝：当前步数超过已知最短路径，无需继续
    
    if (x == ex && y == ey){  // 到达终点，更新最短路径
        ans = min(ans, step);
        return;
    }
    
    for (int i = 0; i < 4; i++){  // 遍历四个方向
        int nx = x + dx[i], ny = y + dy[i];
        // 判断：不越界、未访问、不是障碍
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && vis[nx][ny] == 0 && c[nx][ny] != '#'){
            vis[nx][ny] = 1;  // 标记为已访问
            // 递归：如果是 'x'，步数 +2；否则 +1
            dfs(nx, ny, step + 1 + (c[nx][ny] == 'x'));
            vis[nx][ny] = 0;  // 回溯：撤销标记
        }
    }
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> c[i][j];
            if (c[i][j] == 'r') sx = i, sy = j;  // 记录起点
            if (c[i][j] == 'a') ex = i, ey = j;  // 记录终点
        }
    }
    vis[sx][sy] = 1;  // 起点标记为已访问
    dfs(sx, sy, 0);   // 从起点开始搜索
    if (ans == 1e9) cout << "Impossible";  // 无法到达
    else cout << ans;
    return 0;
}

关键技巧点

• 剪枝：if(step > ans) return; 大幅减少无效搜索。
• 方向数组：dx[] 和 dy[] 简化四个方向的遍历。

---

3. 应用场景二：组合数生成（从 n 个数中选 k 个）

问题描述

从 1~n 中选出 k 个数，按从小到大的顺序输出所有组合（如 n=5, k=3，输出 1 2 3、1 2 4 等）。

核心思路

• 用 pre 记录上一个选的数，保证后续选的数更大（避免重复组合）。
• 用 vector 存储当前已选的数。

代码详解

#include<bits/stdc++.h>
using namespace std;

int n, k;

// 参数：已选 step 个数，上一个选的数是 pre，已选列表 v
void dfs(int step, int pre, vector<int> v){
    if(step == k){  // 已选满 k 个数，输出
        for(int i = 0; i < v.size(); i++){
            cout << v[i] << " ";
        }
        cout << endl;
        return;
    }
    // 从 pre+1 开始选，保证递增
    for(int i = pre + 1; i <= n; i++){
        vector<int> v2 = v;  // 复制当前列表
        v2.push_back(i);      // 加入当前选的数 i
        dfs(step + 1, i, v2); // 递归：选下一个数
    }
}

int main(){
    cin >> n >> k;
    vector<int> v;
    dfs(0, 0, v);  // 初始：已选 0 个，上一个数是 0，列表为空
    return 0;
}

关键技巧点

• pre 变量：强制递增，避免 1 2 3 和 2 1 3 这类重复。
• vector 传值：每次递归复制一份，自动实现回溯（无需手动撤销）。

---

4. 应用场景三：子集枚举（选或不选的决策）

问题描述

有 n 种食材，每种食材有酸度 s[i] 和苦度 k[i]。选择至少一种食材，使得总酸度（乘积）与总苦度（和）的差的绝对值最小。

核心思路

• 枚举所有非空子集（每个食材“选”或“不选”）。
• 用 pre 保证不重复枚举（类似组合数）。

代码详解

#include<bits/stdc++.h>
using namespace std;

int n, s[200], k[200], ans = 1e9;  // s 酸度，k 苦度，ans 最小差值

// 参数：已选 step 个，上一个选的是 pre，已选列表 v
void dfs(int step, int pre, vector<int> v){
    if (step >= 1){  // 只要选了至少一个食材，就计算差值
        int sumS = 1, sumK = 0;
        for (int i = 0; i < v.size(); i++){
            sumS *= s[v[i]];  // 总酸度是乘积
            sumK += k[v[i]];  // 总苦度是和
        }
        ans = min(ans, abs(sumS - sumK));  // 更新最小差值
    }
    // 枚举选下一个食材（从 pre+1 开始，避免重复）
    for (int i = pre + 1; i <= n; i++){
        vector<int> v2 = v;
        v2.push_back(i);
        dfs(step + 1, i, v2);
    }
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s[i] >> k[i];
    vector<int> v;
    dfs(0, 0, v);
    cout << ans;
    return 0;
}

关键技巧点

• 非空子集：if (step >= 1) 确保不选“空集”。
• 乘积与和：注意 sumS 初始化为 1（乘法单位元），sumK 初始化为 0（加法单位元）。

---

5. 应用场景四：全排列生成

问题描述

给定 n 个数，输出它们的所有排列（按字典序）。

核心思路

• 用 vis 数组标记某个数是否已被选过。
• 每次从未选的数中挑一个加入排列。

代码详解

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, a[N], vis[N];  // a 存储数字，vis 标记是否已选

// 参数：已选 step 个数，当前排列 v
void dfs(int step, vector<int> v){
    if(step == n){  // 已选满 n 个数，输出排列
        for(int i = 0; i < v.size(); i++){
            cout << a[v[i]] << " ";  // v[i] 是下标，a[v[i]] 是数值
        }
        cout << endl;
    }
    // 遍历所有数字，选一个未被选过的
    for(int i = 1; i <= n; i++){
        if(vis[i] == 0){  // 第 i 个数未被选过
            vis[i] = 1;    // 标记为已选
            vector<int> v2 = v;
            v2.push_back(i);  // 加入下标 i（不是数值 a[i]）
            dfs(step + 1, v2);
            vis[i] = 0;    // 回溯：撤销标记
        }
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);  // 先排序，保证字典序输出
    vector<int> v;
    dfs(0, v);
    return 0;
}

关键技巧点

• vis 数组：核心是“标记-递归-撤销标记”的回溯模式。
• 字典序：先对 a 数组排序，再按顺序选数，保证输出有序。

---

6. DFS 常见技巧总结

技巧	用途	示例场景
剪枝	提前终止无效搜索，优化时间	迷宫寻路中 step > ans 时返回
vis 数组	标记已访问/已选，避免重复	全排列、迷宫寻路
pre 变量	保证递增/递减，避免重复组合	组合数生成、子集枚举
vector 传值	自动实现回溯（无需手动撤销）	组合数、排列生成
方向数组	简化网格中多方向的遍历	迷宫、棋盘问题