一起动脑筋 · 先看一个小故事
迷宫岔路口有向左和向右两条路。机器人先向左探到底，发现死路，就退回岔口向右试。
把过程摊开来看
- 标记当前格防止重复绕圈
- 试一个方向走进可通行格
- 遇死路返回上一格
- 换方向直到找到或穷尽
DFS 把迷宫看成位置与可走连接组成的图。
每次只走到合法、允许探索的格子，回退后再尝试其他方向。墙壁和边界必须先检查。
01怎样把迷宫变成搜索问题？
把每个可走格子当成一个状态。
状态
当前位置 (row,col)。
起点
入口。
目标
出口。
转移
上下左右走一步。
02DFS 怎样走？
选择一个可走方向→继续深入→死路就退回来
03一个简化代码框架
bool dfs(int r, int c) {
if (r == targetR && c == targetC) {
return true;
}
visited[r][c] = true;
for (四个方向) {
int nr = ...;
int nc = ...;
if (在地图内 && 可以走 && !visited[nr][nc]) {
if (dfs(nr, nc)) {
return true;
}
}
}
return false;
}04为什么必须判断边界？
移动后的位置可能跑到迷宫外面。
因此要先确认：
0 ≤ nr < rows，并且 0 ≤ nc < cols
05为什么一定要 visited？
如果两个格子可以来回走，不记录访问状态就可能无限递归。
A↔B↔A
06怎样记录真正走过的路径？
如果要输出路径，可以在进入节点时记录位置，失败回退时撤销，或者记录父节点，最后从终点反向恢复。
具体方法取决于你需要“一条路径”还是“所有路径”。
07DFS 找到的是最短路吗？
不保证。
你已经知道了什么
- 迷宫可以看成由格子状态组成的搜索问题。
- DFS 会沿一条路深入，失败后回退。
- 边界检查和 visited 都非常重要。
- DFS 可以判断是否可达并找到一条路径。
- DFS 不保证无权迷宫中的最短路径。
下一篇：BFS：像水波一样一层层扩散
轮到你来试一试
左路要走 10 步，右路只要 3 步，先走左路的 DFS 会保证先发现右路吗？
想好了吗？点开看解释
不会。DFS 的策略是先深入选中的分支，不按总步数从小到大探索。