◎学完你会
- 用递归写 DFS（深度优先搜索），在网格/迷宫里一条道走到黑再回溯；
- 理解“标记 → 递归 → 撤销标记”三步，是全排列、子集、走迷宫的共同骨架；
- 知道忘回溯会让搜过的路被当成没搜过，导致答案错或搜爆。
1动一动：DFS 走格子
5×5 网格，从 (0,0) 出发按“右下左上”优先递归走：能进就进，走到头退回再试别的方向。
点「走一步」看递归栈怎么进/退：
初始在 (0,0)。点「走一步」开始 DFS。
绿色=当前格，浅黄=已访问，深黄=正在回溯（从这条道退出来）。
2关键命令：DFS 回溯三步
void dfs(int x, int y){
if(越界 || 已访问) return;
vis[x][y] = 1; // ① 标记
dfs(x, y+1); dfs(x+1, y); // ② 递归四个方向
dfs(x, y-1); dfs(x-1, y);
vis[x][y] = 0; // ③ 回溯：撤销标记
}
全排列本质一样：used[i]=1 → dfs(step+1) → used[i]=0。回溯就是把这次尝试的状态还原，好让兄弟分支重来。
访问过的点要记录：搜过的格子不进第二次，否则递归无限套娃。
⚠易错点
忘回溯（忘撤销标记）：标记后不 vis[x][y]=0，兄弟分支会以为这格已被占，漏解。
漏写递归出口：没有“越界 / 已访问 / 到目标”任一出口，DFS 无限递归直到爆栈。
方向顺序想当然：DFS 的“走法顺序”决定路径形态，但结果覆盖所有可达格，别依赖某一种顺序。
回溯改了共享状态忘还原：数组、used 标记在递归前改、递归后必须还原，否则污染后续分支。
?跨学科：DFS 就是“钻到底再回头”
下迷宫/走山洞：先沿着一条岔路走到头，没路了就退回来试另一条——正是 DFS。
整理抽屉一层层翻到最底、再逐层还原，也是“递归 + 回溯”。
深度优先适合“要找遍所有可能 / 一路推进到深处”的探索；要找“最近/最短路”则看 BFS（下一节）。
✎练一练
DFS 里 vis[x][y]=0（撤销标记）的作用是？
撤销标记 = 回溯，把这次占用让出来，供另一条分支重试；否则该格被永久占住、漏解。
想找“从起点到终点的
最少步数”，应该用 DFS 还是 BFS？
答案：用 BFS。DFS 一条道走到黑，先找到的路径不一定最短；BFS 按层扩散，第一次到达终点的那层就是最短路。DFS 更适合“找是否存在/枚举所有解”。