正确回溯路径的关键是路径容器在递归前push、返回后pop，且visited数组需初始化为false、进入时设true、回溯时设false；用visited比在path中查找更高效可靠，避免重复访问和无限递归。
DFS递归实现时，如何正确回溯路径而不污染其他分支
关键在于路径容器必须在递归调用前 push，递归返回后 pop，且不能传引用给所有子调用——否则一个分支的修改会透传到兄弟分支。常见错误是把 vector<pair>>&</pair> 一路传下去，结果发现走到死路后，前面合法路径也被清空了。
正确做法是：每次递归传值（或局部拷贝），或在函数内维护栈式操作。更推荐后者，性能好、内存可控：
void dfs(int x, int y, vector<pair<int,int>>& path) {
if (x < 0 || y < 0 || x >= n || y >= m || !maze[x][y] || visited[x][y]) return;
if (x == tx && y == ty) { // 到达终点
result = path;
return;
}
visited[x][y] = true;
path.push_back({x, y});
dfs(x+1, y, path);
dfs(x, y+1, path);
dfs(x-1, y, path);
dfs(x, y-1, path);
path.pop_back(); // 回溯：必须放在这里，且仅在此处恢复
visited[x][y] = false;
}为什么用 visited 数组比反复检查 path 更可靠
有人试图用 find(path.begin(), path.end(), make_pair(x,y)) != path.end() 判断是否已访问，这在小迷宫里看似能跑通，但时间复杂度升到 O(L) 每次判断（L 是当前路径长度），整棵树退化成 O(N×L²)，10×10 迷宫就明显卡顿。
visited 是布尔数组或 unordered_set<pair>></pair>，查表是 O(1)；且能准确区分“当前路径经过”和“历史上某条路径经过过”，避免重复进入同一格子导致无限递归。
立即学习“C++免费学习笔记（深入）”；
- 必须初始化为
false，进递归前设true，回溯后设false - 如果只找一条路径，找到后可提前
return，不必等整个 DFS 结束 - 若迷宫含障碍（
maze[i][j] == 0），visited不应标记障碍格——它们本就不能走
vector<pair>></pair> 存路径 vs vector<int></int> 存转向码，哪种更适合调试
存 pair 直观，打印出来就是坐标序列，一眼看出是否绕圈或跳格；存转向码（比如 0=右、1=下、2=左、3=上）省空间，但调试时得反复查表还原坐标，容易看错。
实际开发中建议起步用 vector<pair>></pair>，确认逻辑正确后再优化存储。尤其当需要输出“第几步走到哪”或画图验证时，坐标路径不可替代。
- 打印路径可用：
for (auto [x, y] : result) cout - 注意 C++17 结构化绑定需开启
-std=c++17 - 若编译器不支持，改用
for (const auto& p : result) cout
迷宫输入为字符矩阵时，如何安全转换成 int 网格
别直接写 maze[i][j] == '1' 做判断——万一文件换行符混入、空格没 trim、或末尾有 BOM，'1' 可能读成 '1\n' 或 '\ufeff1'，导致起点识别失败。
稳妥做法是先按行读入 string，再逐字符过滤空白和非法字符，最后映射：
for (int i = 0; i < n; ++i) {
string line;
getline(cin, line);
for (char c : line) {
if (c == '0' || c == '1') {
maze[i][col++] = c - '0'; // 安全转 int
}
}
}更健壮的版本应校验行列数、检查起点终点是否存在、并报告无效字符位置——这些往往才是运行时崩溃的真正原因。
回溯本身不难，难的是边界条件和状态管理。哪怕只是多一个没重置的 visited 标志，或者少一次 pop_back()，路径就会错得毫无规律。
