椰程信奥 · 说课稿

搜索1（DFS） · 说课稿（对应视频 24′01″）　课件共 18 页

一、教材与学情

本讲对应视频《CSP复赛专题14-搜索1（DFS）》（24′01″）。讲解 DFS 的本质（一条路走到黑、再回溯；DFS=递归；回溯是递归返回的副产品），通过迷宫出口、连通块统计、全排列三道例题建立"写 DFS 四步法"的手感，再用填涂颜色（反向搜索）与组合的输出（双参数 DFS）两道拓展体会"换角度"与"天然去重"。

学情上的典型困难：① 把回溯当成额外技巧，忘了写 取消标记 → 只走一条路、漏解； ② 不会判断 vis 该永久还是临时（迷宫可达性可永久，排列/组合必须临时）； ③ 搞不清"全排列要所有顺序、组合只要一种顺序"，导致组合重复；④ 输出格式（%5d / %3d 场宽）写错。

二、教学目标

知识与技能：能说出 DFS 四步法（状态/边界/选择/回溯）；能独立写出迷宫可达性、连通块统计、全排列、填涂颜色、组合输出；理解 vis 标记在不同场景下的"永久 vs 临时"，以及组合双参数 DFS 的递增去重原理。
过程与方法：用 6 个可单步的动画，把"当前格/递归栈/死路回退/used 数组/泛洪/递增"外显化；让学生先猜"下一步往哪走"再点按钮揭示。
情感态度：体会"没有更优解法时，DFS 这种不漏的笨办法就是正确办法"的工程判断；以及"求补集 / 换角度"的解题美感。

三、重点难点

重点

① DFS 四步法；② 回溯=取消标记； ③ 迷宫/连通块的 vis 判否；④ 全排列的"盒子放数字"模板；⑤ 组合双参数 DFS 递增去重。

难点

① vis 永久还是临时；② 填涂颜色为什么要"反向搜索"； ③ 组合为什么必须限制 i 从 x 起；④ 输出场宽格式。

四、教学过程（45 分钟）

环节	时间	教师活动	学生活动	设计意图
① 本质与方法	6′	第 2–3 页：讲"走到黑/回溯"，带出四步法；追问"回溯是不是额外技巧"	口头回答：回溯=递归返回	建立本质认知
② 例题1 迷宫	8′	第 4–5 页动画①：点「下一步」让学生先猜下一格，再揭示"为什么往回走"	预测方向，看递归栈变化	DFS 栈可视化
③ 回溯现场	4′	第 6 页动画②：盯 (0,1) 死路，讲 vis 永久标记	说"为什么标记/为什么往回走"	区分永久/临时标记
④ 例题2 连通块	6′	第 7–8 页动画③：看逐块染色与实时块数	数块数，说为什么从"未访问黑格"启动	多起点启动
⑤ 代码走读	5′	第 9 页：迷宫+连通块代码，强调先写判否再递归	跟读三段判否	固化框架
⑥ 例题3 全排列	7′	第 10–11 页：动画④盒子放数字 + 代码，停在使用 `%5d`	看 used 数组与回溯取回	状态标记模板
⑦ 拓展填色	5′	第 12 页动画⑤：反向搜索，讲"求补集"	预测哪些 0 变 2	换角度
⑧ 拓展组合	3′	第 13 页动画⑥：双参数 DFS，讲递增去重	解释为什么不会重复	天然去重
⑨ 检测	1′	第 14–15 页三道检测	完成测评	形成性评价

五、板书设计

DFS 四步法：定状态 → 找边界 → 列选择 → 写回溯（别忘了取消标记）

迷宫/连通块：先写三个判否（越界 / 不可通行 / 已访问）再递归；vis 可达性可永久

全排列：used[i]=true 放 → dfs → used[i]=false 取回（临时标记）　printf("%5d")

填涂颜色：从边界 0 泛洪标记圈外 → 未标记 0 改 2（反向搜索）

组合：dfs(x,k) 循环 i 从 x 起 → 组合内递增 → 天然去重　setw(3)

六、教学亮点与反思

亮点一：6 个动画全部可单步。学生能亲手停在任意一步，先猜"往哪走"再揭示理由，把 DFS 的"试错"过程变成可推演的模型。
亮点二：用同一套"试—回溯"语言串起 5 道题。迷宫、连通块、排列、填色、组合只是"状态/选择/标记"不同，降低认知负担。
亮点三：明确区分 vis 的两种语义。可达性里永久保留，排列/组合里临时取消——这是学生最易混的点，单独用动画②讲透。
反思：组合与全排列易混淆，建议板书并排对比；输出场宽用真机演示一次 printf 效果更直观。

七、答辩预设

问：既然 BFS 也能搜迷宫，为什么讲 DFS？
答：本专题是搜索（一），先建立"递归=DFS=回溯"这一最通用的心智模型，它适用于所有方案枚举（排列/组合/连通块）。迷宫只问可达性，DFS/BFS 都行；但全排列、组合这类"列出所有方案"的题只能用 DFS。先讲 DFS 是为了覆盖更广。