椰程信奥·互动课件 专题14·搜索1：DFS 深度优先搜索
10:00 1 / 18
🧭 椰程信奥 · CSP复赛专题系列

专题14 · 搜索（一）
DFS 深度优先搜索

DFS 的本质只有八个字：一条路走到黑，再回溯。
它用递归实现，回溯只是递归返回的副产品。当没有更优解法时，这种"笨办法"往往是唯一正确的办法。 本讲用迷宫、连通块、全排列、填色、组合五道题，把 DFS 写熟。

迷宫出口（可达性） 连通块统计 全排列 / 填色 / 组合
路线图

DFS 全景（对应视频 24′01″）

🔧 本质与方法　0–4′

一条路走到黑、再回溯；DFS=递归；回溯是递归的副产品； 写 DFS 的四步法：状态 / 边界 / 选择 / 回溯。

🧩 三道例题　4–16′

迷宫出口（可达性/回溯）、连通块统计（多起点启动）、 全排列（盒子放数字）。

🚀 课后拓展　16–24′

填涂颜色（反向搜索）、组合的输出（双参数 DFS）， 体会"换角度"与"天然去重"。

本讲最重要的一句话：DFS 不是"聪明的算法"，而是"不漏的算法"—— 它把每一种可能都走一遍，所以正确性有保障；代价是可能很慢，但考场里"能对"往往比"快"重要。
本质

一条路走到黑，再回溯

① 什么是"走到黑"

从一个起点出发，沿着一条分支一直往下走，直到走投无路（撞墙 / 到边界 / 已访问 / 选完）。

void dfs(状态){
  if(走投无路) { 处理/返回; }
  for(每个可选方向){
    dfs(下一个状态);   // 继续往下
  }
}

② 什么是"回溯"

走到死路后退回到上一个岔路口，换一条没试过的路。 回溯不是额外的技巧，就是递归返回——返回时把现场恢复（取消标记），DFS 才能去试别的路。

标记现场;
dfs(下一层);
取消标记;   // ← 回溯：递归返回的副产品

状态

函数参数代表什么？
迷宫里是 (x,y)。

边界

什么算"走投无路"？
到终点 / 撞墙 / 越界 / 已访问。

选择

这一步能往哪走？
四方向 / 未用过的数 / 递增的数。

回溯

返回前恢复现场？
vis=false / used=false。

⚠️ 回溯虽"不高效"，但当没有更优解法时它就是必需。 很多题（全排列、组合、所有方案枚举）只有"把所有可能试一遍"这一条路，DFS 正是干这个的。
3D🎲 DFS = 一条路走到底，撞墙就回溯🖱 拖拽旋转 · 双击复位
为什么用 3D：平面迷宫看不出「深度优先」的深度在哪。立体迷宫里墙是立起来的柱子，学生能看出 DFS 是钻进去、碰壁、退一步。
例题1

迷宫出口：判断 A 能否到 B

n 行 n 列迷宫，0 可通行、1 不可通行。从起点 A 出发，四方向（上下左右）移动，问能否到达终点 B。

要点

  • 四方向遍历：用方向数组 dx/dy 枚举上下左右。
  • 三个判否：越界 / 已访问 / 不可通行（值为 1）——任一成立都不能走。
  • 现场标记与回溯：进入格子先标记已访问；若此路不通，递归返回后取消标记，让别的路径还能走它。
  • 目标是可达性（只问"能不能到"），不是"最短路径"，所以 DFS 足够。
下页用动画走一遍：当前格、递归栈、死路回退，全程写明"为什么往回走 / 为什么标记"。
动画①

看递归栈怎么长、怎么退

红 = 当前所在格；深红 = 当前路径（递归栈）；灰 = 已探索过的死路；白 = 未访问；深色 = 墙。

样例
DFS 递归栈（栈顶=当前格）
点「下一步」开始。先走 (0,0)。
动画②

vis 标记 → 递归返回 → 取消标记

同一套 DFS，重点看三种颜色如何随递归进出变化。

样例
当前路径（递归栈里）
已回溯 / 已探索（离开路径）
未访问
墙（不可通行）
注意 (0,1) 是个死路：进去后四方向都走不通 → 为什么往回走（无未访问相邻格）→ 为什么标记（避免重复进入死循环）。
✅ 关键区分：迷宫"可达性"里 vis 是永久的（探索过就不必再来）； 而全排列 / 组合里 used 是临时的（递归返回要取消标记）。本动画演示的是"探索过即留下灰色痕迹"的永久标记版。
例题2

连通块：数一数有几片黑格

n 行 m 列方格图，四连通规则下，统计黑格（标 1）被分成了几个独立的连通块。

// 思路：
// 1. 扫一遍全图，遇到"没访问过的黑格"
// 2. 以它为起点启动一次 DFS，把整片连在一起
//    的黑格全部标记成"已访问"（同一块同色）
// 3. 每启动一次 DFS，块数 +1
int ans = 0;
for(i..n) for(j..m)
  if(g[i][j]==1 && !vis[i][j]){
    ans++; dfs(i, j);     // 第 ans 块
  }

为什么要从"未访问黑格"启动

每块只会被它的第一个被扫到的黑格触发一次 DFS；DFS 内部把整块标成已访问， 所以每个块恰好被数一次，不重不漏。下一页用动画实时看染色过程。

动画③

逐块染色，实时显示块数

每遇到一个未访问黑格，启动一次 DFS 把它整片染成同一种颜色；不同连通块用不同颜色。

点「下一步」：每启动一次 DFS，块数 +1，并把那一片黑格染成新颜色。
当前连通块数：0
例题1+2

迷宫 + 连通块 完整代码（标准写法）

// 迷宫可达性（核心框架）
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool vis[35][35];
bool ok;

void dfs(int x, int y){
  if(x==Bx && y==By){ ok=true; return; }
  for(int d=0; d<4; d++){
    int nx=x+dx[d], ny=y+dy[d];
    if(越界) continue;
    if(g[nx][ny]==1) continue;      // 不可通行
    if(vis[nx][ny]) continue;       // 已访问
    vis[nx][ny]=true;              // ① 标记
    dfs(nx, ny);
    // 可达性：vis 永久，回溯可不取消标记
  }
}
// 连通块统计（每块启动一次）
void dfs2(int x, int y, int id){
  col[x][y]=id;                 // 染成第 id 块
  vis[x][y]=true;
  for(int d=0; d<4; d++){
    int nx=x+dx[d], ny=y+dy[d];
    if(越界) continue;
    if(g[nx][ny]!=1) continue;   // 只走黑格
    if(vis[nx][ny]) continue;
    dfs2(nx, ny, id);
  }
}
// 主循环：ans=0;
// if(g==1 && !vis) ans++, dfs2(x,y,ans);
坑：方向数组写错顺序、或漏掉三个判否之一，都会漏走 / 越界 RE。先写判否，再递归是最稳的顺序。
例题3

全排列：往 n 个盒子里放数字

生成 1~n 的所有全排列。把"排列"想象成 n 个盒子，每个盒子放一个还没用过的数字。

模拟思路

① 第 1 个盒子从小到大试 1,2,3…；放下 1 后，标记 used[1]=true；
② 递归去放第 2 个盒子，只能放没标记的数字；
③ 放满 n 个盒子 → 得到一个排列，输出；
④ 回溯：把刚放的数字取出来（used=false），让下一个排列能用它。

输出格式

每个数字占 5 个场宽：printf("%5d", x)。 例如 n=3 第一行是 1 2 3（数字前有 4 个空格）。

✅ 这样写天然按字典序（因为盒子总是从小到大试数字），且不重复（used 保证一个数字只出现一次）。这是 DFS 最经典的"状态标记 + 回溯"模板。
动画④

6 个排列是怎么一个个长出来的

n=3。红 = 当前盒子里的数字；灰底 = used 已用；白底 = 可用。看 used 数组与回溯取回。

规模
used 数组：
点「下一步」：在第 1 个盒子放 1，递归放第 2 个…放满就输出，然后取回数字回溯。
已生成排列：0 个
例题3

全排列 · 完整代码

int n;
int ans[20];
bool used[20];

void dfs(int pos){          // 正在放第 pos 个盒子
  if(pos == n){           // 放满了
    for(int i=0;i<n;i++)
      printf("%5d", ans[i]);
    printf("\n");
    return;
  }
  for(int i=1;i<=n;i++)
    if(!used[i]){
      used[i]=true;      // ① 标记
      ans[pos]=i;
      dfs(pos+1);          // ② 递归
      used[i]=false;     // ③ 回溯取回
    }
}

int main(){
  cin >> n;
  dfs(0);
}
坑① 忘记回溯 used[i]=false： 数字被永久占用，后面的排列永远凑不齐 → 只输出一个排列甚至一个都没有。
坑② 场宽写错： 题目要求 5 个场宽，写成 %d 或 %3d 都会格式错误（洛谷 P1706 严格比对空格）。
✅ 模板迁移：盒子放数字 = "选数"类 DFS 的通用骨架， 组合、子集、八皇后都是它的亲戚。
拓展

填涂颜色：换角度 = 反向搜索

方格含由 1 构成的闭合圈。正向找"圈内"很难，反过来：从边界的 0 泛洪标记圈外，剩下的 0 就是圈内，改成 2。

从边界 0 出发泛洪（浅蓝=圈外）。泛洪结束后，没被标记的 0（白）变成 2（黄）。
圈外(已标记) 圈内(→2) 1 墙
✅ 这题的精髓是"角度"：直接判定圈内 = 难；判定圈外（从边界可达）= 一次普通 DFS/BFS。 把"求补集"当成武器，很多题都能这样化难为易。
拓展

组合的输出：双参数 DFS 天然去重

从 1~n 取 r 个，不分顺序、按字典序输出。双参数 dfs(x, k)：x=起始数，k=已选个数。

样例
点「下一步」：每一步从 x 起选数 i，递归 dfs(i+1, k+1)。因为只往后选 → 组合内递增 → 天然去重。
已生成组合：0 个（共 C(5,3)=10 个）

为什么必须递增

若允许回头选小数，会同时产生 1 2 3 和 3 2 1 这种同一组合的不同顺序 → 重复。 强制 i 从 x 起 让每个组合只以一种顺序出现。

对比全排列

全排列要"所有顺序都出现" → 不限制起点；组合"顺序无关" → 限制递增。 同一套 DFS 骨架，差一个参数就换了语义。

诊断

DFS 易错辨析

① 全排列里漏写 used[i] = false;（回溯取回）会怎样？

② 迷宫"可达性"用 DFS，vis 标记能不能在回溯时取消？

③ 填涂颜色正向找"圈内 0"很难，正确做法是？

拿分

一道题 100 分是分档给的——不会正解也要先拿保底

复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。

第 1 档 特判 5~10 分 约 2 分钟 第 2 档 暴力 20~30 分 约 8 分钟 第 3 档 特殊性质 40~60 分 约 15 分钟 第 4 档 正解 100 分 约 25 分钟

① 特判档：先别想算法，看数据范围表

题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行， 就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。

② 暴力档：按题意最直白地写一遍

多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。

③ 特殊性质档：题目里那句「若……」

常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。

④ 正解档：思路定了，就赢了八成

考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。

考场纪律：每档设时间上限，到点还没调通就 立刻提交当前版本，保住已有分数，再往上冲。最常见的翻车是"正解写了 50 分钟没过，连暴力分都没交上去"。
拿分

本讲 3 道题，各自的四档怎么走

全排列问题 · PERM

第1档 · 2 分钟
n == 1 → 输出 1

第2档 · 8 分钟
递归枚举每一位放哪个数，n ≤ 8 稳过

第3档 · 10 分钟
用 next_permutation 直接按字典序输出

第4档 · 15 分钟
DFS + used 数组 + 回溯恢复现场，输出用 %5d

填涂颜色 · FILL

第1档 · 2 分钟
没有 1（没有闭合圈）→ 原样输出

第2档 · 8 分钟
对每个 0 做 BFS 看能否走到边界，n ≤ 30 稳过

第3档 · 10 分钟
只有一行/一列是 1 → 直接判

第4档 · 15 分钟
从边界开始洪水填充标记「圈外 0」，剩下的 0 改成 2

组合的输出 · COMB

第1档 · 2 分钟
r == 1 → 每个数一行；r == n → 只有一行

第2档 · 8 分钟
枚举所有 r 元组再判递增，n ≤ 10 稳过

第3档 · 10 分钟
只做 r == 2 的双重循环版本

第4档 · 15 分钟
DFS 递增选数（保证字典序），每层从上一个数 +1 开始

50 分钟时间盒（一题的节奏）：
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查 freopen 与文件名。
课堂上别让学生"从头想正解"。先要求每个人 15 分钟内交出第 1、2 档， 再放开冲正解。这个顺序一换，平均分通常能涨一大截——因为它杜绝了"想了 40 分钟，交上去 0 分"。
当堂检测

椰程信奥当堂测评

① 组合输出 dfs(x, k) 里，循环写成 for(i=1; i<=n; i++)（不限制从 x 起）会怎样？

② 连通块统计"每启动一次 DFS 块数+1"，起点必须选？

③ 全排列输出要求每个数字占 5 个场宽，应写？

椰程锦囊 · 写 DFS 的四步 + 一问
四步：定状态 → 找边界 → 列选择 → 写回溯；
写完必问一句：这一步走不通时，会不会回到岔路口去试别的路？（忘了回溯 = 只走一条，漏解）
再加一条工程判断：没有更优解法时，DFS 这种"笨办法"就是正确答案。💡

目录