把 DFS 放进网格迷宫：每个通路格是一个节点，相邻通路格之间有一条边——迷宫求解就成了"从起点 S 到出口 E 的图搜索"。网格 DFS 的特色是方向顺序：每走进一格，按固定次序（本动画为右 → 下 → 左 → 上）尝试四邻，第一个没去过的方向就扎进去；四个方向全撞墙或已走过，这一格就被判定为死胡同，回溯到上一格换方向。走到死胡同再退出来，正是 DFS 与"碰壁"短兵相接的样子。
本动画在 6×4 的小迷宫上演完整求解（S 左上 (0,0)，E 左下 (3,0)）：
S . . . . . 右上 (0,5)、右下 (3,5) 是两处死胡同，
. . # . . # (1,3) 是死角；(3,2) 封死左下走廊——
. . # . . # DFS 必须先进死胡同、再长链回退，
. . # . . E 最后改道左列才摸到 E。
节拍：访问拍一格（入路径），死路拍一拍（标红 + 光点折返），E 前共有 3 处主动撞壁 + 一整段右侧分支的连锁回退。全片 30 拍（2s/拍 ≈ 60s）：访问 17 格、死路标注 11 拍，最终路径只剩 6 格——被标红的 11 格就是 DFS 替你排除的错误答案。
访问 (r,c) ｜ 入路径 / 回溯 (r,c) ｜ 死路 / ✓ 完成 ｜ 访问 17 格 · 路径 6——访问数含死路格，路径数只算最终从 S 到 E 的那一条。| 项目 | 复杂度 | 说明 |
|---|---|---|
| 时间 | O(R·C) | 每格至多进出一次（访问过即不再入）；本动画 17 格访问、无重复 |
| 空间 | O(R·C) | 递归栈 / 路径栈最深等于最长蛇形通道；visited 标记 O(R·C) |
| 找到的路 | 不保证最短 | 是"一条"通路，不一定是最短通路；最短路请用 BFS |
#include <iostream>
using namespace std;
const int R = 4, C = 6;
int maze[R][C] = { // 0 = 通路，1 = 墙
{0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 1},
{0, 0, 1, 0, 0, 1},
{0, 0, 1, 0, 0, 0},
};
bool vis[R][C];
int pathR[R * C], pathC[R * C], len = 0; // 当前路径栈
// 右、下、左、上；找到 E 即一路返回 true（剪枝）
bool dfs(int r, int c) {
vis[r][c] = true;
pathR[len] = r; pathC[len] = c; len++; // 入路径
cout << "访问 (" << r << "," << c << ")\n";
if (r == 3 && c == 0) return true; // 到达 E
int dr[] = {0, 1, 0, -1}, dc[] = {1, 0, -1, 0};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
if (maze[nr][nc] == 0 && !vis[nr][nc] && dfs(nr, nc))
return true;
}
len--; // 回溯：出路径
cout << "回溯 (" << r << "," << c << ") ｜ 死路\n";
return false;
}
int main() {
dfs(0, 0); // 终路径 6 格：(0,0)(0,1)(1,1)(2,1)(3,1)(3,0)
return 0;
}
迷宫/网格上问"有没有路""走出所有路径""最大连通区域"时，网格 DFS 是第一反应：洪水填充（flood fill）、岛屿问题、扫雷展开，全是它的马甲。它还有一个 BFS 给不了的妙用：记录完整当前路径——路径栈里始终躺着"从 S 到这里走了哪几步"，适合需要输出具体走法的场景。要最短出路时换 BFS（首次到达即最短）；带权网格（进门要钥匙、格子有代价）则轮到 Dijkstra。实现上最容易错的是边界与访问标记：出界先判、进格先标，漏一步就是死循环或重复访问——本动画里每个红格都在提醒你：这一格曾经被认真走进去过。