矩阵最长路径DFS回溯中visited标记置false的作用疑问

需求为在仅包含0和1的矩阵中，查找从给定起点到终点、所有途经节点值均为1的最长路径。
对应实现代码如下：

function longestPath02(matrix, startPosition, endPosition) {
    let maxDistance = 0;
    const visited = {};

    function isValidCoordinate(i, j) {
        // 校验坐标是否在合法范围内
        if (i > matrix.length - 1 || i < 0 || j > matrix[0].length - 1 || j < 0) return false;
        // 校验坐标值为1且未被访问
        if ((matrix[i] || [])[j] !== 1 || visited[`${i},${j}`]) return false;
        return true;
    }

    function calculate(startPosition, endPosition, distance) {
        const [i, j] = startPosition;
        const [x, y] = endPosition;

        if (i === x && j === y) {
            maxDistance = Math.max(distance, maxDistance);
            return;
        }

        visited[`${i},${j}`] = true;

        if (isValidCoordinate(i + 1, j)) calculate([i + 1, j], endPosition, distance + 1);
        if (isValidCoordinate(i - 1, j)) calculate([i - 1, j], endPosition, distance + 1);
        if (isValidCoordinate(i, j + 1)) calculate([i, j + 1], endPosition, distance + 1);
        if (isValidCoordinate(i, j - 1)) calculate([i, j - 1], endPosition, distance + 1);

        visited[`${i},${j}`] = false; // 存在疑问的回溯代码
    }

    calculate(startPosition, endPosition, 0);
    return maxDistance;
}

核心疑问：递归遍历完当前节点的四个方向分支后，为什么要将当前坐标的visited访问标记重置为false？移除该行后运行结果错误，该操作的作用与必要性是什么？

解答 #

这个重置操作是回溯算法的标准「状态复位」步骤，必要性完全由算法逻辑和问题目标决定：

• 首先明确visited的作用范围：这份代码用深度优先搜索(DFS)枚举所有从起点到终点的无环合法路径，再从中挑出最长的一条。visited标记只对当前正在探索的单条路径生效——它的唯一作用是避免同一条路径里重复走同一个节点，绕圈死循环。
• 为什么必须复位：当你把当前节点(i,j)四个方向的所有可能分支都探索完，意味着所有「以(i,j)为固定途经点」的路径都已经计算完毕，接下来要退回上一层递归，去探索不经过当前节点的其他路径分支。如果这时候不把(i,j)的访问标记改回false，这个标记会错误残留到其他完全独立的路径分支中，导致本来合法可走的节点被误判为“已在当前路径中访问过”，直接漏掉大量可能存在的更长路径。
• 直观类比：你可以把这个过程想象成走迷宫拿粉笔做标记——走某条岔路的时候，给途经的路口画标记，提醒自己“当前这条路已经走过这个路口，别绕圈”；等这条岔路走到头（不管是死路还是终点），退回到上一个岔路口试其他方向的时候，必须把刚才这条岔路画的标记擦掉。不然试其他路的时候看到之前的标记，会误以为这个路口已经在当前走的路上来过，直接放弃通行，大量能到终点的路线根本不会被探索到。
• 去掉该行的后果：第一次DFS遍历碰到的路径上的所有节点会被永久标记为已访问，后续其他合法路径只要经过这些节点都会被直接判定为非法，相当于你根本没有枚举所有可能路径，只算了第一条遍历到的路径长度，结果必然错误。

补充说明：如果是用BFS找最短路径，节点标记为已访问后不需要重置，因为BFS第一次到达节点时走的就是最短路径，后续到达该节点的路径只会更长，无需考虑。但找最长路径必须枚举所有无环路径，同一个节点可以出现在不同的合法路径里，只是不能在单条路径中重复出现，因此必须做回溯状态复位。

测试数据集：

let mat = [
    [1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
    [1, 0, 1, 0, 1, 1, 1, 0, 1, 1],
    [1, 1, 1, 0, 1, 1, 0, 1, 0, 1],
    [0, 0, 0, 0, 1, 0, 0, 1, 0, 0],
    [1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
    [1, 0, 0, 0, 1, 0, 0, 1, 0, 1],
    [1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
    [1, 1, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 1, 1, 0, 1, 0, 0],
];
console.log(longestPath02(mat, [0, 0], [5, 7]));

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