DFS回溯易“走不出去”或漏解，因未区分访问标记与路径标记：仅用全局visited数组且未在回溯时撤销，或未及时弹出路径点；应进入时标记、退出时撤销，用vector配合递归栈管理路径。
为什么 DFS 回溯在迷宫中容易“走不出去”或漏解
因为没正确区分「访问标记」和「路径标记」：只用一个 visited 数组，会导致回溯时无法还原路径状态；或者在递归返回前忘了把当前点从路径容器中弹出。迷宫里每个格子可以多次经过（比如绕路），但一条合法路径里不能重复访问同一格子——这个约束必须靠「进入时标记 + 退出时撤销」来动态维护。
-
visited应该是局部作用域的路径状态，不是全局静态标记；推荐直接用std::vector<:vector>></:vector>配合递归栈生命周期管理，或更稳妥地用函数参数传递副本 - 路径记录建议用
std::vector<:pair int>></:pair>，每次递归调用前push_back，返回前pop_back；避免用全局变量，否则多路递归会互相污染 - 方向数组顺序影响搜索结果（比如优先下→右→上→左），但不影响是否找到解；若只要一个解，找到后应立即
return true并逐层跳出，别继续搜
如何写一个带路径返回的 DFS 函数（C++11 及以上）
核心是让函数返回 bool 表示是否找到路径，并通过引用参数把路径“带出来”。不要试图用返回值传整个路径（效率低且易误判空路径）。
bool dfs(const std::vector<std::vector<int>>& maze,
int x, int y,
std::vector<std::pair<int, int>>& path,
std::vector<std::vector<bool>>& visited) {
int n = maze.size(), m = maze[0].size();
if (x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == 1 || visited[x][y]) {
return false;
}
if (x == n-1 && y == m-1) { // 到达终点
path.push_back({x, y});
return true;
}
visited[x][y] = true;
path.push_back({x, y});
// 四个方向：上下左右（可按需调整顺序）
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
for (int i = 0; i < 4; ++i) {
if (dfs(maze, x + dx[i], y + dy[i], path, visited)) {
return true;
}
}
path.pop_back(); // 回溯：撤销当前点
visited[x][y] = false; // 回溯：释放访问标记
return false;
}
注意：visited 和 path 都是引用传入，但 visited 在每轮递归中被修改并恢复，确保子路径互不干扰；path 是累积构建的，只在成功时保留，失败则靠 pop_back 撤销。
迷宫输入为字符时怎么处理障碍和起点终点
常见输入是 vector<string></string>，其中 '#' 是墙，'.' 是空地，'S' 起点，'E' 终点。这时候不能直接套用数值判断逻辑，得先扫描找起点，并统一转成 0/1 矩阵或现场解析。
立即学习“C++免费学习笔记（深入）”；
- 先遍历一遍找
'S'坐标，作为dfs的初始x,y；终点位置可不预存，进递归后遇到'E'就返回 true - 边界检查仍要保留，但单元格判断改成：
grid[x][y] == '#'→ 障碍，grid[x][y] == 'E'→ 成功 - 如果起点是
'S'，记得在path初始就加入它，且visited对应位置设为true
为什么用 stack 模拟 DFS 容易丢路径或栈溢出
手动用 std::stack 实现非递归 DFS 时，每个栈元素不仅要存坐标，还得存「当前路径」或至少存「父节点指针」。如果只压入 {x, y}，根本没法重建完整路径；若每次压入完整 vector 副本，空间爆炸，尤其在大迷宫中。
- 递归 DFS 天然携带调用栈上的路径上下文，回溯干净利落；非递归版本必须额外维护一个「前驱映射」（如
map<pair>, pair<int>></int></pair>）来反向还原路径 - 深度过深（比如 1000×1000 迷宫最坏情况）可能触发栈溢出，此时应改用 BFS 或限制递归深度 +
std::stack显式模拟，但路径重建逻辑复杂度陡增 - 除非题目明确要求非递归，否则别为了“避免递归”而硬写迭代版——可读性、正确性和调试成本都更高
真正难的不是写出 DFS，而是想清楚：路径是“过程态”还是“结果态”，以及每一步的标记和撤销是否严格对称。少一个 pop_back，或多一个 visited[x][y] = true 放错位置，结果就全乱了。
