基于DFS的迷宫求解算法出现死循环问题排查求助

问题根因 #

• 未标记已访问路径：这是死循环的核心原因。你的代码每次仅判断下一个格子是否为通路"1"，但没有标记已经走过的格子，会出现从A走到B后，B的方向判断又返回走A，两个格子来回递归调用，永远无法终止。
• 变量名不统一：向上走的判断逻辑中错误使用了未定义的matrix变量，而非传入的迷宫参数m，运行时会直接抛出引用错误。
• 缺少数组越界判断：没有对坐标的合法性做校验，当坐标已经在边界时，访问x+1/x-1/y+1/y-1会出现数组越界，引发未知错误。
• 终止逻辑不完整：找到出口后仅return当前递归层，没有标记搜索成功，递归还会继续回溯走其他分支，浪费性能。
• 方向注释错误：原代码中y+1是向右走，y-1是向左走，注释写反会影响代码可读性。

修复方案 #

修复逻辑：先校验坐标合法性，访问过的通路标记为非"1"的值避免重复走，找到出口后返回成功标识终止所有递归，回溯时同步清理路径栈。

function solve(m, s, x, y) {
    // 校验当前坐标合法性
    if (x < 0 || x >= m.length || y < 0 || y >= m[0].length) {
        return false;
    }
    // 终止条件：到达最后一行且是通路，找到出口
    if (x == 9 && m[x][y] == "1") {
        s.push(x + ", " + y);
        return true;
    }
    // 判断当前坐标是否为未访问的通路
    if (m[x][y] != "1") {
        return false;
    }
    // 标记当前坐标已访问，避免重复走
    m[x][y] = "2";
    // 把当前坐标加入路径
    s.push(x + ", " + y);

    // 四个方向搜索，只要有一个方向找到出口就直接返回
    if (solve(m, s, x + 1, y)) { // 下
        return true;
    }
    if (solve(m, s, x, y + 1)) { // 右
        return true;
    }
    if (solve(m, s, x, y - 1)) { // 左
        return true;
    }
    if (solve(m, s, x - 1, y)) { // 上
        return true;
    }

    // 四个方向都走不通，回溯：弹出当前坐标，返回失败
    s.pop();
    return false;
}

函数调用后如果返回true，栈s中就存储了从起点到终点的完整路径。如果不需要修改原迷宫数组，可以提前拷贝一份副本再传入函数。

内容的提问来源于stack exchange，提问作者Bryar