如何获取骑士从一个位置到另一位置的完整最短路径？

你的代码存在几个核心逻辑错误，导致无法正确追踪路径，以下是问题分析和修复后的实现：

原代码的关键问题 #

• 队列与访问集合存储错误：你把移动方向存入队列和visited，而非计算后的目标坐标，完全偏离了追踪路径的逻辑。
• 边界判断逻辑混乱：!visited.has(directions[d] && possibleX >=0 ...) 里的逻辑短路写法错误，应该先判断坐标是否在棋盘范围内，再检查是否已访问。
• 路径追踪机制缺失：单一的path数组无法记录每个节点的完整路径，需要为每个队列元素绑定对应的路径信息。

修复后的代码 #

function knightMoves(start, end) {
    const directions = [[1, 2], [1, -2], [-1, 2], [-1, -2], [2, 1], [2, -1], [-2, 1], [-2, -1]];
    // 队列存储对象：包含当前坐标和到达该坐标的完整路径
    const queue = [{ position: start, path: [start] }];
    // 用字符串存储已访问坐标（数组无法直接作为Set的键）
    const visited = new Set([`${start[0]},${start[1]}`]);

    while (queue.length > 0) {
        const { position, path } = queue.shift();
        const [x, y] = position;

        // 到达终点，返回路径
        if (x === end[0] && y === end[1]) {
            console.log(`最短路径长度: ${path.length - 1}步`);
            return path;
        }

        // 遍历所有可能的移动方向
        for (const [dx, dy] of directions) {
            const newX = x + dx;
            const newY = y + dy;
            const key = `${newX},${newY}`;

            // 检查坐标是否在8x8棋盘内，且未被访问
            if (newX >= 0 && newX < 8 && newY >= 0 && newY < 8 && !visited.has(key)) {
                visited.add(key);
                // 生成新路径并加入队列
                queue.push({
                    position: [newX, newY],
                    path: [...path, [newX, newY]]
                });
            }
        }
    }

    // 理论上不会执行到这里，因为骑士总能到达任意方格
    return [];
}

// 测试用例
console.log(knightMoves([0,0],[1,2])); // [[0,0],[1,2]]
console.log(knightMoves([0,0],[3,3])); // [[0,0],[1,2],[3,3]]
console.log(knightMoves([3,3],[0,0])); // [[3,3],[1,2],[0,0]]

核心修复点说明 #

1. 队列元素结构：每个队列元素包含当前位置和到达该位置的完整路径，确保每一步都能回溯完整路线。
2. 访问集合处理：将坐标转为字符串（如"0,0"）存入visited，避免数组作为键的判断错误。
3. 棋盘边界修正：将原代码的<=8改为<8，因为标准国际象棋棋盘是8x8，坐标范围为0-7。
4. 路径生成：每次生成新坐标时，基于当前路径创建新数组，保证每个路径独立不干扰。

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