博客详情 - BCOI

gf25055 的博客
《死亡笔记-代码模板》DFS答题模板
gf25055 LV 8 @ 2026-3-19 13:55:44

一、连通块问题 / 洪水填充（Flood Fill）典型场景：二维网格中统计连通块数量、最大连通块面积、改变连通块标记等。方向通常为四方向或八方向。

模板（四方向，统计数量或面积）

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

const int MAXN = 1005;
int n, m;
int grid[MAXN][MAXN];          // 地图，0/1表示或字符表示
bool vis[MAXN][MAXN];          // 访问标记

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

// DFS 函数：返回从 (x, y) 出发的连通块大小（用于面积统计）
int dfs(int x, int y) {
    vis[x][y] = true;
    int cnt = 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 
            && !vis[nx][ny] && grid[nx][ny] == 1) {
            cnt += dfs(nx, ny);
        }
    }
    return cnt;
}

// 主逻辑：遍历所有格子
int main() {
    // 输入 n, m, grid ...
    memset(vis, 0, sizeof(vis));
    int blocks = 0, maxArea = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (!vis[i][j] && grid[i][j] == 1) {
                blocks++;
                int area = dfs(i, j);
                maxArea = max(maxArea, area);
            }
        }
    }
    cout << "连通块数量: " << blocks << endl;
    cout << "最大面积: " << maxArea << endl;
    return 0;
}

模板要点方向数组：dx/dy 定义移动方式，四方向或八方向。

边界与条件判断：在递归前判断 nx, ny 合法性，以及是否符合填充条件（如 grid[nx][ny] == 目标值）。

访问标记：vis 数组防止重复访问和死循环。

返回值设计：如果只计数，可以不返回；若需面积，则累加子问题的返回值。

二、地图路径问题（找一条可行路径或所有路径）典型场景：迷宫从起点到终点是否存在路径，或者输出所有路径。与 Flood Fill 不同的是，DFS 过程中需要回溯，因为一条路径探索完后要撤销标记，以便其他路径尝试经过该格子。

模板（找一条路径，存在即停止）

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

const int MAXN = 100;
int n, m;
int maze[MAXN][MAXN];          // 0可走，1障碍
bool vis[MAXN][MAXN];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool found = false;
vector<pair<int, int>> path;   // 记录当前路径

void dfs(int x, int y, int ex, int ey) {
    if (found) return;          // 已经找到，剪枝
    if (x == ex && y == ey) {
        found = true;
        // 输出路径（可选）
        for (auto p : path) 
            cout << "(" << p.first << "," << p.second << ") ";
        cout << endl;
        return;
    }

    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 
            && !vis[nx][ny] && maze[nx][ny] == 0) {
            vis[nx][ny] = true;
            path.push_back({nx, ny});
            dfs(nx, ny, ex, ey);
            path.pop_back();           // 回溯
            vis[nx][ny] = false;       // 回溯
        }
    }
}

int main() {
    // 输入迷宫、起点(sx,sy)、终点(ex,ey)
    memset(vis, 0, sizeof(vis));
    vis[sx][sy] = true;
    path.push_back({sx, sy});
    dfs(sx, sy, ex, ey);
    if (!found) cout << "无路径" << endl;
    return 0;
}

模板要点回溯操作：在递归返回后，需要将 vis 和 path 恢复到进入前的状态，以便其他分支使用。

剪枝：若只需一条路径，可用 found 标记快速终止后续搜索。

路径记录：用 vector 存储坐标对，方便输出。

三、地图最小步数问题（DFS 带步数记录与剪枝）说明：求最短路径/最小步数时，BFS 是更自然的选择，因为 BFS 首次到达即为最短。但有时题目强制要求 DFS 思路，或状态空间特殊需要回溯尝试，我们可以用 DFS + 最优性剪枝（记录当前已知最短步数，超过则停止搜索）。

模板（DFS 求最短路径长度）

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

const int MAXN = 100;
int n, m;
int maze[MAXN][MAXN];
bool vis[MAXN][MAXN];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int minSteps = INT_MAX;  // 全局记录最小步数

// step 表示当前已经走的步数（不包括起点）
void dfs(int x, int y, int ex, int ey, int step) {
    // 最优性剪枝：当前步数已不小于已知最小，无需继续
    if (step >= minSteps) return;
    // 到达终点，更新最小步数
    if (x == ex && y == ey) {
        minSteps = min(minSteps, step);
        return;
    }

    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 
            && !vis[nx][ny] && maze[nx][ny] == 0) {
            vis[nx][ny] = true;
            dfs(nx, ny, ex, ey, step + 1);
            vis[nx][ny] = false;   // 回溯
        }
    }
}

int main() {
    // 输入起点(sx,sy),终点(ex,ey)
    memset(vis, 0, sizeof(vis));
    vis[sx][sy] = true;
    dfs(sx, sy, ex, ey, 0);
    if (minSteps == INT_MAX) 
        cout << "无法到达" << endl;
    else 
        cout << "最短步数: " << minSteps << endl;
    return 0;
}

模板要点最优性剪枝：if (step >= minSteps) return; 极大提升效率，避免冗余搜索。

回溯标记：vis 必须恢复，因为不同路径可能经过相同格子。

复杂度：DFS 最坏情况下仍是指数级，只适用于规模很小的图，或作为理解回溯思想的练习。

四、排列组合问题（回溯法模板）这类问题抽象为：从 n 个元素中选取若干个（可重复/不可重复），按一定顺序排列或组合。DFS 通过 used 数组或 start 索引控制元素是否被选过。

全排列（元素不重复，顺序有关）

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

vector<int> nums;          // 原始数据
vector<int> path;          // 当前排列
vector<bool> used;         // 标记是否已使用
vector<vector<int>> res;   // 存储所有排列

void dfs() {
    if (path.size() == nums.size()) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (!used[i]) {
            used[i] = true;
            path.push_back(nums[i]);
            dfs();
            path.pop_back();
            used[i] = false;
        }
    }
}

// 调用
used.assign(nums.size(), false);
dfs();

组合（元素不重复，顺序无关，如 C(n, k)）

vector<int> nums;
vector<int> path;
vector<vector<int>> res;
int k;  // 要选多少个

// start 参数保证不重复选择之前的元素
void dfs(int start) {
    if (path.size() == k) {
        res.push_back(path);
        return;
    }
    for (int i = start; i < nums.size(); ++i) {
        path.push_back(nums[i]);
        dfs(i + 1);          // 下一层从 i+1 开始，避免重复组合
        path.pop_back();
    }
}

子集（包含空集）

vector<int> nums;
vector<int> path;
vector<vector<int>> res;

void dfs(int start) {
    res.push_back(path);    // 每个节点都加入结果（包括空集）
    for (int i = start; i < nums.size(); ++i) {
        path.push_back(nums[i]);
        dfs(i + 1);
        path.pop_back();
    }
}

模板要点排列：用 used 数组，每层循环都从 0 开始。

组合/子集：用 start 索引控制顺序，避免产生 [1,2] 和 [2,1] 这样的重复。

剪枝：若要求去重（如原数组有重复元素），需先排序，然后在循环中加入 if (i > start && nums[i] == nums[i-1]) continue; 来跳过相同元素。

五、综合 DFS 题目（多状态、复杂约束）综合题可能融合了地图、状态、计数等要素，比如：在网格中找单词（单词搜索）、数独求解、N 皇后等。这类题目 DFS 状态通常包含多个维度（坐标、已匹配长度、已用数字标记等）。

示例：单词搜索（网格中查找给定单词）

bool exist(vector<vector<char>>& board, string word) {
    int m = board.size(), n = board[0].size();
    vector<vector<bool>> vis(m, vector<bool>(n, false));
    
    function<bool(int, int, int)> dfs = [&](int x, int y, int idx) {
        if (idx == word.size()) return true;        // 全部匹配
        if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y] || board[x][y] != word[idx]) 
            return false;
        
        vis[x][y] = true;
        bool found = dfs(x+1, y, idx+1) || dfs(x-1, y, idx+1) ||
                     dfs(x, y+1, idx+1) || dfs(x, y-1, idx+1);
        vis[x][y] = false;
        return found;
    };
    
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (dfs(i, j, 0)) return true;
    return false;
}

模板要点多参数传递：除了坐标，还要传递当前匹配进度 idx。

及时剪枝：边界、访问、字符不匹配立即返回。

回溯：因为需要尝试不同路径，标记必须恢复。

总结对比：DFS vs BFS 适用场景问题类型常用算法理由连通块/Flood Fill DFS/BFS 均可，DFS 递归简洁，BFS 可避免栈溢出（网格大时）地图最短路径/最少步数 BFS BFS 首次到达即为最短，DFS 需全局记录最小值并剪枝，效率低找任意一条可行路径 DFS 可以提前返回，BFS 也能做，但 DFS 配合回溯更容易输出具体路径排列组合/子集/回溯枚举 DFS 本质是回溯树遍历，DFS 自然模拟决策过程，BFS 几乎不用于此复杂状态搜索（数独等） DFS 状态树深度优先搜索，配合剪枝和启发式策略（如 DLX）效率高

《死亡笔记-代码模板》DFS答题模板

状态

开发

支持

关于

《死亡笔记-代码模板》DFS答题模板

状态

开发

支持

关于

登录