DFS 课堂笔记

一、洪水填充（Flood Fill）算法

1. 核心概念

洪水填充是DFS在二维网格上的典型应用，类比“在起点打开水龙头，水会沿上下左右漫延，覆盖所有连通的符合条件的区域”。

• 适用场景：连通块统计、可达性判断、区域染色、封闭区域识别
• 基础配置：定义四方向偏移数组，统一处理上下左右移动

int dx[] = {1, 0, -1, 0}; // 行偏移：下、右、上、左
int dy[] = {0, 1, 0, -1}; // 列偏移

2. 基础题型：可达性判断

题目特征：给定起点和终点，判断能否从起点走到终点（0可走、1为障碍）。

• 递归参数：当前坐标 (x, y)
• 核心逻辑：标记已访问 → 遍历四方向 → 合法则递归深入

bool vis[105][105]; // 标记格子是否走过
void dfs(int x, int y) {
    // 可在此处添加「到达终点」的判断与返回
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        // 先判边界，再判可走、未访问，避免数组越界
        if (nx>=1 && nx<=n && ny>=1 && ny<=n 
            && a[nx][ny]==0 && !vis[nx][ny]) {
            vis[nx][ny] = true;
            dfs(nx, ny);
        }
    }
}

3. 进阶题型：封闭区域染色（圈内填充）

题目特征：n×n矩阵中1为围墙、0为空地，将被围墙完全包围的空地染成指定颜色（如2）。

核心原理

• 接触矩阵边界的0连通块，一定是「圈外」区域
• 完全不接触边界的0连通块，就是被1包围的「圈内」区域
• 解题流程：遍历每个0连通块 → 判断是否触碰边界 → 未触碰则整体染色

修正后标准代码（含原代码bug修复）

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

const int MAXN = 105;
int n, a[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool is_inside;      // 标记当前连通块是否在圈内
struct node { int x, y; };
vector<node> v;      // 存储当前连通块的所有坐标

void dfs_check(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        // 越界 = 连通块触边 = 判定为圈外
        if (nx < 1 || nx > n || ny < 1 || ny > n) {
            is_inside = false;
            continue; // 越界直接跳过，禁止访问数组
        }
        
        // 边界合法 + 是空地 + 未访问
        if (a[nx][ny] == 0 && !vis[nx][ny]) {
            vis[nx][ny] = true;
            v.push_back({nx, ny});
            dfs_check(nx, ny);
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    
    // 遍历所有格子，处理未访问的空地
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j] == 0 && !vis[i][j]) {
                v.clear();
                is_inside = true;  // 先假设在圈内
                vis[i][j] = true;
                v.push_back({i, j});
                dfs_check(i, j);
                
                // 未触边则为封闭区域，统一染色
                if (is_inside) {
                    for (auto &p : v)
                        a[p.x][p.y] = 2;
                }
            }
        }
    }
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << a[i][j] << " ";
        cout << endl;
    }
    return 0;
}

本题高频易错点

1. 变量误用：原代码出现未定义的m，实际应为n
2. 越界访问：越界判断后必须跳过，不能再访问数组，否则会运行错误
3. 起点漏标记：进入DFS前，必须先把起点标记为已访问
4. 状态未重置：每次处理新连通块前，必须清空vector、重置is_inside

二、DFS求解排列与组合问题

1. 组合问题（无顺序、不重复选取）

题目特征：从n个数中选m个，不考虑顺序，输出所有方案。

• 核心思想：只往后选，不回头
• 用pre记录上一次选择的下标，每次从pre+1开始枚举，天然去重
• 无需vis标记数组

标准模板

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, a[N];

// step: 已选个数  pre: 上一次选的下标  rec: 存储已选数字
void dfs_comb(int step, int pre, vector<int> rec) {
    if (step == m) { // 递归出口：选够m个，输出
        for (auto x : rec) cout << x << " ";
        cout << endl;
        return;
    }
    // 从pre+1开始选，保证下标递增、方案不重复
    for (int i = pre + 1; i <= n; i++) {
        vector<int> tmp = rec;
        tmp.push_back(a[i]);
        dfs_comb(step + 1, i, tmp);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n); // 保证字典序输出
    dfs_comb(0, 0, {});
    return 0;
}

2. 排列问题（有顺序、不重复选取）

题目特征：从n个数中选m个，考虑顺序，输出所有排列。

• 核心思想：标记是否用过
• 用vis[]数组标记数字是否被选中
• 每次从1到n全量枚举，未使用则选中
• 递归返回后必须回溯（撤销标记），供其他分支使用

标准模板

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, a[N];
bool vis[N];

void dfs_perm(int step, vector<int> rec) {
    if (step == m) {
        for (auto x : rec) cout << x << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {        // 数字未被使用
            vis[i] = true;    // 标记已使用
            vector<int> tmp = rec;
            tmp.push_back(a[i]);
            dfs_perm(step + 1, tmp);
            vis[i] = false;   // 关键：回溯，撤销标记
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    dfs_perm(0, {});
    return 0;
}

3. 组合与排列核心区别

三、DFS通用解题四步走

1. 定出口：明确递归终止条件（选够m个、到达终点、遍历完所有方向）
2. 定参数：明确递归需要携带的状态信息（坐标、步数、上一个选择、记录数组）
3. 枚举选择：遍历所有合法的下一步方向/数字
4. 状态回溯：排列、选数类题目，递归返回后必须恢复现场

四、高频易错点提醒

1. 数组越界：二维网格必须先判断边界，再访问数组元素
2. 起点漏标记：进入DFS前，必须先标记当前点已访问
3. 回溯遗漏：排列问题递归返回后，必须将vis改回false
4. 全局变量未重置：多组数据、多个连通块场景，必须初始化全局状态
5. 下标不统一：全程保持1下标或0下标一致，避免混乱