GESP6级C++考试语法知识（二十五、深度优先搜索（五、DFS终极奥义））

⚔️第五课《DFS终极奥义》——原来算法世界到处都是 DFS一、故事开始算法圣殿1、经过前四课。小骑士 DFS 已经成为了DFS 小勇者2、但是。算法王国最深处。还有一座“dfs算法圣殿”3、dfs算法圣殿有迷宫是 DFS全排列是 DFS岛屿问题是 DFS八皇后也是 DFS数独也是 DFS4、小骑士震惊“为什么这么多问题 居然全都是 DFS”5、今天。我们就要真正理解DFS 的终极奥义二、DFS 的真正本质是什么1、很多同学以为DFS 是dfs(...)这个函数。其实不是。2、DFS 真正本质“尝试所有可能”3、只要问题满足当前状态 ↓ 可以做选择 ↓ 进入下一状态那么很可能就是 DFS4、DFS 万能思维模板① 当前状态是什么② 下一步有哪些选择③ 做一个选择④ 进入下一层⑤ 回来恢复现场这就是所有 DFS 的共同灵魂⚔️第一部分《迷宫为什么是 DFS》1、迷宫问题例如S . . # # . . . E2、DFS 在做什么1当前位置(x,y)2下一步选择上 下 左 右3于是尝试一种方向 ↓ 继续搜索 ↓ 走不通回来 ↓ 换方向4这就是 DFS3、迷宫 DFS 最核心代码for(int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; dfs(nx,ny); }4、本质“试每一种走法”5、参考代码#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 success false; // 四个方向 int dx[4] {1,-1,0,0}; int dy[4] {0,0,1,-1}; 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) { success true; return; } vis[x][y] true; // 四方向搜索 for(int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; dfs(nx,ny); } } int main() { dfs(0,0); if(success) cout 能到终点; else cout 不能到终点; return 0; }⚔️第二部分《全排列为什么是 DFS》1、问题1 2 3组成所有排列。2、DFS 在做什么当前位置当前已经选了哪些数字例如[1,2]3、下一步选择还能选哪个数字例如34、于是选一个数字 ↓ 继续搜索 ↓ 回来 ↓ 撤销选择5、这也是 DFS6、经典代码for(int i 1; i n; i) { if(vis[i]) continue; path.push_back(i); vis[i] true; dfs(); vis[i] false; path.pop_back(); }7、真正本质“尝试每一种排列可能”8、参考代码#include iostream #include vector using namespace std; vectorint path; bool vis[10]; int n 3; void dfs() { // 已经选满 if(path.size() n) { for(int i 0; i path.size(); i) cout path[i]; cout endl; return; } // 尝试每个数字 for(int i 1; i n; i) { // 已使用 if(vis[i]) continue; // 做选择 path.push_back(i); vis[i] true; // 搜索下一层 dfs(); // 恢复现场 vis[i] false; path.pop_back(); } } int main() { dfs(); return 0; }⚔️第三部分《岛屿问题为什么是 DFS》1、问题1 1 0 1 0 1 0 0 1统计岛屿数量。2、DFS 在干什么找到一个陆地↓把整个岛全部搜出来3、本质不断扩散 ↓ 不断搜索邻居4、代码核心dfs(nx,ny);不断搜周围。5、这里 DFS 像什么像病毒扩散或者颜料染色这类问题叫连通块问题6、参考代码#include iostream using namespace std; int a[10][10] { {1,1,0,0}, {1,0,0,1}, {0,0,1,1}, {0,0,0,0} }; bool vis[10][10]; int n 4; int m 4; int dx[4] {1,-1,0,0}; int dy[4] {0,0,1,-1}; void dfs(int x,int y) { // 出界 if(x 0 || x n || y 0 || y m) return; // 海洋 或 已访问 if(a[x][y] 0 || vis[x][y]) return; vis[x][y] true; // 搜索四周 for(int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; dfs(nx,ny); } } int main() { int cnt 0; for(int i 0; i n; i) { for(int j 0; j m; j) { // 找到新岛屿 if(a[i][j] 1 !vis[i][j]) { dfs(i,j); cnt; } } } cout 岛屿数量 cnt; return 0; }⚔️第四部分《八皇后为什么是 DFS》1、八皇后问题在棋盘放8个皇后要求互相不能攻击2、皇后攻击规则不能同行同列同斜线3、DFS 在做什么1当前状态已经放了哪些皇后。2下一步选择下一行放哪里3于是尝试一个位置 ↓ 继续放下一个皇后 ↓ 冲突则回来 ↓ 换位置4这其实就是“高级版全排列”4、八皇后简化版void dfs(int row) { if(row 8) { ans; return; } for(int col 0; col 8; col) { if(能放) { 放皇后; dfs(row 1); 移除皇后; } } }5、真正本质“尝试每一种摆放方案”6、参考代码#include iostream #include cmath using namespace std; int pos[10]; int n 8; int ans 0; // 检查当前位置能不能放皇后 bool check(int row,int col) { // 检查前面已经放过的皇后 for(int i 0; i row; i) { // 同列 if(pos[i] col) return false; // 同斜线 if(abs(i - row) abs(pos[i] - col)) return false; } return true; } // DFS搜索 void dfs(int row) { // 已经放完8行 if(row n) { ans; cout 第 ans 种方案 endl; // 输出棋盘 for(int i 0; i n; i) { for(int j 0; j n; j) { if(pos[i] j) cout Q ; else cout . ; } cout endl; } cout endl; return; } // 尝试这一行的每一列 for(int col 0; col n; col) { // 能放 if(check(row,col)) { // 放皇后 pos[row] col; // 搜索下一行 dfs(row 1); // 不需要手动恢复 // 因为 pos[row] 下一次会被覆盖 } } } int main() { dfs(0); cout 总方案数 ans endl; return 0; }⚔️第五部分《数独为什么也是 DFS》1、数独问题填数字1~9要求每行不重复每列不重复每宫不重复2、DFS 在做什么1当前状态已经填了哪些格子。2下一步选择当前空格填什么数字3于是尝试填1 ↓ 不行 ↓ 回来 ↓ 尝试填2 ↓ 继续搜索4这就是回溯 DFS3、数独代码思想简化for(int num 1; num 9; num) { if(能填) { 填数字; dfs(下一个空格); 擦掉数字; } }4、真正本质“尝试所有填法”5、参考代码#include iostream using namespace std; int a[4][4] { {1,0,0,4}, {0,0,1,0}, {0,1,0,0}, {2,0,0,3} }; bool check(int x,int y,int num) { // 检查行 for(int i 0; i 4; i) { if(a[x][i] num) return false; } // 检查列 for(int i 0; i 4; i) { if(a[i][y] num) return false; } return true; } bool dfs(int x,int y) { // 下一行 if(y 4) { x; y 0; } // 完成 if(x 4) return true; // 已经有数字 if(a[x][y] ! 0) return dfs(x,y1); // 尝试填数字 for(int num 1; num 4; num) { if(check(x,y,num)) { a[x][y] num; if(dfs(x,y1)) return true; // 恢复现场 a[x][y] 0; } } return false; } int main() { dfs(0,0); for(int i 0; i 4; i) { for(int j 0; j 4; j) cout a[i][j] ; cout endl; } return 0; }三、同学们突然发现1、原来这些题虽然长得不一样。但本质完全一样2、迷宫尝试走法3、排列尝试顺序4、岛屿尝试扩散5、八皇后尝试摆放6、数独尝试填数7、本质全都是做选择 ↓ 进入下一层 ↓ 搜索 ↓ 回来 ↓ 恢复现场四、DFS 真正强大的地方1、DFS 的威力在于“暴力尝试所有可能”2、很多超级难题。其实本质都是搜索3、例如AI 搜索游戏走法自动解谜棋类程序路径规划很多都和 DFS 有关系。五、DFS 最终万能模板1、同学们最终形成“DFS 思维模板”第一步当前状态是什么第二步有哪些选择第三步尝试一个选择。第四步进入下一层。第五步回来恢复现场。2、最终模板void dfs(当前状态) { if(结束条件) { 处理答案; return; } for(每一种选择) { if(合法) { 做选择; dfs(下一状态); 恢复现场; } } }六、本章总结1、DFS 不是一个代码模板。2、DFS 真正是“搜索所有可能性”的思想3、只要问题满足能做选择 ↓ 能进入下一步 ↓ 需要尝试所有可能4、那么它很可能就是 DFS七、真正学懂 DFS 的同学1、最后会达到一种境界看到题目时。脑子里会自动出现搜索树2、并且自动思考当前状态是什么 下一步能做什么 是否需要回溯3、这时。同学们就真正掌握 DFS 了