第二课《迷宫王国大冒险——二维 BFS》一、故事开始迷宫王国的宝藏1、很久以前在「迷宫王国」里藏着一颗神秘宝石。2、小骑士阿勇接到了任务找到宝藏3、可是问题来了迷宫里有墙壁有陷阱有死胡同4、而且阿勇必须走最短路线5、于是他想“这次不能用 DFS 乱冲了”因为DFS 容易一条路冲到底结果绕远路。6、这次应该使用BFS的方法于是他按照BFS方法上路了。二、今天同学们要学什么今天是二维 BFS上一课我们在一维“数字线”上移动。今天我们进入️二维地图三、认识地图坐标1、假设地图长这样S . . # # . . . . . # E2、这里S 起点 E 终点 # 墙 . 可以走3、地图中的位置怎么表示使用坐标4、例如(行, 列)比如(1) 左上角(0,0)(2) 终点(2,3)四、在地图里怎么移动小骑士每次可以⬆️上⬇️下⬅️左➡️右这叫四方向移动五、方向数组这是 BFS 的经典的技巧1、方向数组int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};2、什么意思1第0个方向(-1, 0)表示向上走2第1个方向(1, 0)表示向下走3第2个方向(0, -1)表示向左走4第3个方向(0, 1)表示向右走六、BFS 如何搜索迷宫1、假设阿勇在(0,0)2、BFS 会1第1层搜索一步能到的位置。2第2层搜索两步能到的位置。3第3层搜索三步能到的位置。3、像不像水波扩散七、为什么 BFS 一定最短这是今天最核心的问题1、因为BFS 是按层搜索的2、它的搜索方式第一层1步到达第二层2步到达第三层3步到达.......3、所以第一次到终点一定是最少步数4、这就是BFS 最强大的地方八、visited 二维数组1、上一课我们用vis[x]2、今天地图是二维的。所以vis[x][y]3、表示(x,y) 是否来过4、为什么必须有 visited否则阿勇会这样左 → 右 → 左 → 右无限绕圈九、地图越界问题初学者易错1、假设地图大小n 行 m 列2、合法位置必须满足0 x n 0 y m3、否则就会走出地图十、第一道迷宫题1、题目地图S . . # # . . . . . # E2、要求求最少步数十一、BFS 参考程序#include iostream #include queue using namespace std; struct Node { int x; int y; int step; }; char mp[105][105]; bool vis[105][105]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; int main() { int n 3; int m 4; // 地图 char temp[3][4] { {S,.,.,#}, {#,.,.,.}, {.,.,#,E} }; // 复制地图 for(int i 0; i n; i) { for(int j 0; j m; j) { mp[i][j] temp[i][j]; } } queueNode q; // 起点 q.push({0,0,0}); vis[0][0] true; while(!q.empty()) { Node cur q.front(); q.pop(); int x cur.x; int y cur.y; // 到达终点 if(mp[x][y] E) { cout 最少步数 cur.step endl; return 0; } // 枚举四个方向 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] mp[nx][ny] ! #) { vis[nx][ny] true; q.push({nx, ny, cur.step 1}); } } } cout 无法到达终点 endl; return 0; }十二、程序执行过程1、开始(0,0)进入队列。2、然后扩展(0,1)3、再扩展(1,1) (0,2)4、继续像水波一样。5、最终第一次到达E时一定最短十三、二维 BFS 模板二维 BFS 四步法第一步起点入队。第二步取出队头。第三步枚举四个方向。第四步合法就入队。十四、新手易犯的错误❌错误1忘记 visited会无限循环。❌错误2忘记判断边界数组越界。❌错误3墙壁也进入队列必须mp[nx][ny] ! #❌错误4step 不加1下一层步数必须cur.step 1十五、什么时候想到二维 BFS以后看到1、迷宫2、️最短路径3、最少移动次数4、扩散问题5、火焰蔓延6、病毒感染就要想到BFS是不是可以⚔️十六、课堂挑战题 ⚔️挑战1地图S . # . . . # . E求最少步数。挑战2如果小骑士还能斜着走怎么办提示方向数组要改成八方向十七、本课总结1、二维 BFS 的本质在地图上进行层层扩散2、BFS 的核心工具queue 队列3、方向数组专门处理移动方向4、第一次到终点一定最短5、visited 必不可少防止重复进入今天同学们真正学会的不只是走迷宫的方法。而要掌握“地图中的最短路思维”。
GESP6级C++考试语法知识（二十七、广度优先搜索（二、二维BFS））
第二课《迷宫王国大冒险——二维 BFS》一、故事开始迷宫王国的宝藏1、很久以前在「迷宫王国」里藏着一颗神秘宝石。2、小骑士阿勇接到了任务找到宝藏3、可是问题来了迷宫里有墙壁有陷阱有死胡同4、而且阿勇必须走最短路线5、于是他想“这次不能用 DFS 乱冲了”因为DFS 容易一条路冲到底结果绕远路。6、这次应该使用BFS的方法于是他按照BFS方法上路了。二、今天同学们要学什么今天是二维 BFS上一课我们在一维“数字线”上移动。今天我们进入️二维地图三、认识地图坐标1、假设地图长这样S . . # # . . . . . # E2、这里S 起点 E 终点 # 墙 . 可以走3、地图中的位置怎么表示使用坐标4、例如(行, 列)比如(1) 左上角(0,0)(2) 终点(2,3)四、在地图里怎么移动小骑士每次可以⬆️上⬇️下⬅️左➡️右这叫四方向移动五、方向数组这是 BFS 的经典的技巧1、方向数组int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};2、什么意思1第0个方向(-1, 0)表示向上走2第1个方向(1, 0)表示向下走3第2个方向(0, -1)表示向左走4第3个方向(0, 1)表示向右走六、BFS 如何搜索迷宫1、假设阿勇在(0,0)2、BFS 会1第1层搜索一步能到的位置。2第2层搜索两步能到的位置。3第3层搜索三步能到的位置。3、像不像水波扩散七、为什么 BFS 一定最短这是今天最核心的问题1、因为BFS 是按层搜索的2、它的搜索方式第一层1步到达第二层2步到达第三层3步到达.......3、所以第一次到终点一定是最少步数4、这就是BFS 最强大的地方八、visited 二维数组1、上一课我们用vis[x]2、今天地图是二维的。所以vis[x][y]3、表示(x,y) 是否来过4、为什么必须有 visited否则阿勇会这样左 → 右 → 左 → 右无限绕圈九、地图越界问题初学者易错1、假设地图大小n 行 m 列2、合法位置必须满足0 x n 0 y m3、否则就会走出地图十、第一道迷宫题1、题目地图S . . # # . . . . . # E2、要求求最少步数十一、BFS 参考程序#include iostream #include queue using namespace std; struct Node { int x; int y; int step; }; char mp[105][105]; bool vis[105][105]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; int main() { int n 3; int m 4; // 地图 char temp[3][4] { {S,.,.,#}, {#,.,.,.}, {.,.,#,E} }; // 复制地图 for(int i 0; i n; i) { for(int j 0; j m; j) { mp[i][j] temp[i][j]; } } queueNode q; // 起点 q.push({0,0,0}); vis[0][0] true; while(!q.empty()) { Node cur q.front(); q.pop(); int x cur.x; int y cur.y; // 到达终点 if(mp[x][y] E) { cout 最少步数 cur.step endl; return 0; } // 枚举四个方向 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] mp[nx][ny] ! #) { vis[nx][ny] true; q.push({nx, ny, cur.step 1}); } } } cout 无法到达终点 endl; return 0; }十二、程序执行过程1、开始(0,0)进入队列。2、然后扩展(0,1)3、再扩展(1,1) (0,2)4、继续像水波一样。5、最终第一次到达E时一定最短十三、二维 BFS 模板二维 BFS 四步法第一步起点入队。第二步取出队头。第三步枚举四个方向。第四步合法就入队。十四、新手易犯的错误❌错误1忘记 visited会无限循环。❌错误2忘记判断边界数组越界。❌错误3墙壁也进入队列必须mp[nx][ny] ! #❌错误4step 不加1下一层步数必须cur.step 1十五、什么时候想到二维 BFS以后看到1、迷宫2、️最短路径3、最少移动次数4、扩散问题5、火焰蔓延6、病毒感染就要想到BFS是不是可以⚔️十六、课堂挑战题 ⚔️挑战1地图S . # . . . # . E求最少步数。挑战2如果小骑士还能斜着走怎么办提示方向数组要改成八方向十七、本课总结1、二维 BFS 的本质在地图上进行层层扩散2、BFS 的核心工具queue 队列3、方向数组专门处理移动方向4、第一次到终点一定最短5、visited 必不可少防止重复进入今天同学们真正学会的不只是走迷宫的方法。而要掌握“地图中的最短路思维”。
