⚔️第五课《DFS终极奥义》
——原来算法世界到处都是 DFS！
🌟一、故事开始：算法圣殿
1、经过前四课。
小骑士 DFS 已经成为了：
🌟DFS 小勇者！
2、但是。
算法王国最深处。
还有一座：
🌟“dfs算法圣殿”
3、dfs算法圣殿有：
🌟迷宫是 DFS
🌟全排列是 DFS
🌟岛屿问题是 DFS
🌟八皇后也是 DFS
🌟数独也是 DFS
4、小骑士震惊：
“为什么这么多问题， 居然全都是 DFS？！”5、🌟今天。
我们就要真正理解：
DFS 的终极奥义！
🌟二、DFS 的真正本质是什么？
1、很多同学以为：
DFS 是：
dfs(...)这个函数。
其实不是。
2、🌟DFS 真正本质：
“尝试所有可能”
3、只要问题满足：
当前状态 ↓ 可以做选择 ↓ 进入下一状态那么：
很可能就是 DFS！
4、DFS 万能思维模板
🌟① 当前状态是什么？
🌟② 下一步有哪些选择？
🌟③ 做一个选择
🌟④ 进入下一层
🌟⑤ 回来恢复现场
🌟这就是所有 DFS 的共同灵魂！
⚔️第一部分《迷宫为什么是 DFS？》
1、🌟迷宫问题
例如：
S . . # # . . . E2、🌟DFS 在做什么？
（1）当前位置：
(x,y)（2）下一步选择：
上 下 左 右（3）于是：
尝试一种方向 ↓ 继续搜索 ↓ 走不通回来 ↓ 换方向（4）🌟这就是 DFS！
3、🌟迷宫 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、🌟这也是 DFS！
6、🌟经典代码
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; vector<int> 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）🌟这就是：
回溯 DFS！
3、🌟数独代码思想（简化）
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,y+1); // 尝试填数字 for(int num = 1; num <= 4; num++) { if(check(x,y,num)) { a[x][y] = num; if(dfs(x,y+1)) 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、🌟这时。
同学们就真正：
