GESP6级C++考试语法知识（二十一、深度优先搜索（一、DFS 一条路走到黑））

第一课《迷宫探险队》——DFS 到底是什么一、故事开始勇敢的小骑士1、很久很久以前在算法王国里有一座神秘的迷宫城堡。2、城堡里面有墙壁有陷阱有死路还有一颗“黄金宝石”✨3、国王说“谁能找到宝石谁就是最聪明的小勇士”4、于是。小骑士 DFS 出发了二、小骑士是怎么找路的1、小骑士的方法非常简单✅ 能往前走就一直往前走2、如果前面是墙或者没路了3、那就✅ 退回来再换一条路继续试。4、这就是 DFSDFS 中文叫深度优先搜索什么意思5、“深度优先”是什么意思就是一条路先走到底例如A → B → C → D能继续走决不回头只有A → B → C → D ❌没路了才会退回 C然后看看还有没有别的路三、不要急着写代码我们先真正理解DFS 到底在干什么。1、迷宫地图我们有这样一个迷宫S . . # # # . # . . . E其中符号意思S起点E终点#墙.能走2、小骑士开始出发从 S 开始设定方向是向右走第一步S → .第二步继续走S → . → .第三步发现右边是墙#怎么办退回来于是← 回退再尝试别的方向。3、DFS 的核心动作其实只有两件事✅ 1. 往前搜✅ 2. 走不通就回来四、DFS 和栈有什么关系1、我们前面学过栈Stack栈的特点后进先出LIFO2、例如1压进去 2压进去 3压进去出来时3先出来 2再出来 1最后出来3、DFS 其实也一样例如A ↓ B ↓ C ↓ D现在 D 走不通了。会怎么退4、答案D回来 → C回来 → B回来是不是特别像栈5、所以DFS 本质 不断深入不断返回五、现在开始真正写 DFS1、任务判断是否能从 S 走到 E2、地图我们用0 能走 1 墙例如0 0 0 1 1 1 0 1 0 0 0 0终点是(2,3)六、 DFS 参考程序#include iostream using namespace std; int maze[10][10] { {0,0,0,1}, {1,1,0,1}, {0,0,0,0} }; bool vis[10][10]; int n 3; int m 4; bool found false; void dfs(int x,int y) { // 出界 if(x 0 || x n || y 0 || y m) return; // 墙 或 已经走过 if(maze[x][y] 1 || vis[x][y]) return; // 到达终点 if(x 2 y 3) { found true; return; } // 标记走过 vis[x][y] true; // 四个方向 dfs(x1,y); // 下 dfs(x-1,y); // 上 dfs(x,y1); // 右 dfs(x,y-1); // 左 } int main() { dfs(0,0); if(found) cout 能到终点; else cout 到不了终点; return 0; }七、理解代码不要背我们一步一步看。1. dfs(x,y)意思“从当前位置开始搜索”例如dfs(0,0)表示从左上角开始。2. 出界判断if(x 0 || x n || y 0 || y m) return;什么意思例如走到(-1,0)已经飞出地图了所以直接返回3. 墙壁判断if(maze[x][y] 1) return;说明撞墙了不能走4. visited 数组vis[x][y]表示“这里以前来过吗”为什么需要它否则会无限绕圈例如A ↔ B会变成A→B→A→B→A→B……程序永远停不下来5. 标记已经来过vis[x][y] true;意思“这里我来过啦”6. 四个方向搜索dfs(x1,y); dfs(x-1,y); dfs(x,y1); dfs(x,y-1);表示上下左右都试试看八、程序真正运行时是什么样开始dfs(0,0)接着往右dfs(0,1)再往右dfs(0,2)再往下dfs(1,2)最后dfs(2,3)找到终点九、DFS 最核心的一句话DFS 的本质当前点 ↓ 尝试下一步 ↓ 继续搜索 ↓ 走不通就返回十、本课总结今天学会了什么✅ 什么是 DFS一条路先走到底✅ DFS 的核心动作往前搜退回来✅ 为什么需要 vis防止死循环。✅ DFS 和栈的关系DFS 的返回过程像栈一样。✅ 我们的第一个 DFS 程序同学们已经会判断能否到终点二维 DFS四方向搜索十一、课后挑战请同学们挑战1修改地图自己设计迷宫。挑战2增加障碍物。看看还能不能到终点。挑战3把dfs顺序改掉。例如先左后右。观察搜索顺序有什么变化下节课预告下一节⚔️《递归魔法与搜索树》孩子会真正理解为什么 dfs() 能自己回来以及搜索树到底是什么