C++ 深度优先搜索（DFS）学习笔记

AC君（自闭中）

2026-02-06 14:10:38

发布于：浙江

1阅读

0回复

0点赞

AI帮忙的地方我都标注了

📌 核心思想：一条路走到黑，走不通就回溯
💡 适用场景：全排列、组合、迷宫、连通块、树/图遍历、回溯类问题(千问AI生成)
dfs模版：

void dfs(当前状态, 其他参数) {
    // ✅ 终止条件（必须先写！）
    if (满足结束条件) {
        res.push_back(path); // 或处理结果
        return;
    }
    
    // 🔁 遍历所有选择
    for (每个可选分支) {
        if (该分支不可行) continue; // 剪枝
        
        // 🌱 做出选择
        标记选择;      // visited[i]=true / path.push_back()
        修改状态;      // 如 sum += val
        
        // 🔄 递归深入
        dfs(新状态, ...);
        
        // 🔙 回溯撤销（关键！）
        撤销标记;      // visited[i]=false / path.pop_back()
        恢复状态;      // sum -= val
    }
}
//自己编写，AI修改

总的来说，深搜有3个步骤——进，回，离
进：进入递归
回：回溯
离：离开函数
只要掌握这3点递归dfs不是问题

另外，dfs还有一个很重要的步骤——剪枝
剪枝指的是减去不必要的递归，使代码的时间复杂度更低
例如A7991.迷宫
如果不剪枝，那么代码如下

#include <iostream>
using namespace std;
const int N = 30;
int sx,sy;
int ex,ey;
char a[N][N];
bool vis[N][N];
int n,m;
int ans = 1e9;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
void dfs(int x,int y,int t)
{
    if(x == ex&&y == ey)
    {
        ans = min(ans,t);
        return ;
    }
    for(int i = 0;i < 4;i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(a[nx][ny] =='W')
        {
            dfs(nx,ny,t+1);
        }
        if(ny >= 1&&ny <= m&&nx >= 1&&nx <= n&&vis[nx][ny] == 0&&a[nx][ny] == '.')
        {
            vis[nx][ny] = 1;
            dfs(nx,ny,t+1);
            vis[nx][ny] = 0;
        }
        if(ny >= 1&&ny <= m&&nx >= 1&&nx <= m&&vis[nx][ny] == 0&&a[nx][ny] >= '0'&&a[nx][ny] <= '9')
        {
            vis[nx][ny] = 1;
            dfs(nx,ny,t+1+(a[nx][ny] - '0'));
            vis[nx][ny] = 0;
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            cin >> a[i][j];
            if(a[i][j] == 'Z')
            {
                sx = i;
                sy = j;
            }
            if(a[i][j] == 'W')
            {
                ex = i;
                ey = j;
            }
        }
    }
    vis[sx][sy] = 1;
    dfs(sx,sy,0);
    if(ans != 1e9) cout << ans;
    else cout << "IMPOSSIBLE";
}

时间为1ms 击败了30.27%的用户

加上剪枝后代码

#include <iostream>
using namespace std;
const int N = 30;
int sx,sy;
int ex,ey;
char a[N][N];
bool vis[N][N];
int mint[N][N];
int n,m;
int ans = 1e9;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
void dfs(int x,int y,int t)
{
    if(x == ex&&y == ey)
    {
        ans = min(ans,t);
        return ;
    }
    if(mint[x][y] != 0)
    {
        if(t > mint[x][y])
        {
            return ;
        }
        else
        {
            mint[x][y] = t;
        }
    }
    else
    {
        mint[x][y] = t;
    }
    for(int i = 0;i < 4;i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(a[nx][ny] =='W')
        {
            dfs(nx,ny,t+1);
        }
        if(ny >= 1&&ny <= m&&nx >= 1&&nx <= n&&vis[nx][ny] == 0&&a[nx][ny] == '.')
        {
            vis[nx][ny] = 1;
            dfs(nx,ny,t+1);
            vis[nx][ny] = 0;
        }
        if(ny >= 1&&ny <= m&&nx >= 1&&nx <= m&&vis[nx][ny] == 0&&a[nx][ny] >= '0'&&a[nx][ny] <= '9')
        {
            vis[nx][ny] = 1;
            dfs(nx,ny,t+1+(a[nx][ny] - '0'));
            vis[nx][ny] = 0;
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            cin >> a[i][j];
            if(a[i][j] == 'Z')
            {
                sx = i;
                sy = j;
            }
            if(a[i][j] == 'W')
            {
                ex = i;
                ey = j;
            }
        }
    }
    vis[sx][sy] = 1;
    dfs(sx,sy,0);
    if(ans != 1e9) cout << ans;
    else cout << "IMPOSSIBLE";
}