JavaScript骑士跳棋最短路径实现问题求助（课程作业）

修复后的完整代码 #

// 初始化8x8棋盘的访问标记数组
const visited = Array.from({ length: 8 }, () => Array(8).fill(false));
// 骑士的8种移动方向
const moves = [
  { x: 2, y: 1 }, { x: 1, y: 2 },
  { x: -1, y: 2 }, { x: -2, y: 1 },
  { x: -2, y: -1 }, { x: -1, y: -2 },
  { x: 1, y: -2 }, { x: 2, y: -1 }
];

function knightsMove(startX, startY, endX, endY) {
  // 队列元素：{x: 当前坐标x, y: 当前坐标y, path: 到达此点的路径数组}
  const queue = [{ x: startX, y: startY, path: [[startX, startY]] }];
  // 标记起点已访问
  visited[startX][startY] = true;

  while (queue.length > 0) {
    const current = queue.shift();

    // 检查是否到达终点
    if (current.x === endX && current.y === endY) {
      console.log("找到最短路径：", current.path);
      return `路径：${current.path.map(coord => `(${coord[0]},${coord[1]})`).join(" → ")}`;
    }

    // 遍历所有可能的移动方向
    for (const move of moves) {
      const newX = current.x + move.x;
      const newY = current.y + move.y;

      // 检查坐标是否在棋盘范围内，且未被访问过
      if (newX >= 0 && newX < 8 && newY >= 0 && newY < 8 && !visited[newX][newY]) {
        visited[newX][newY] = true;
        // 生成新路径：基于当前路径添加新坐标
        const newPath = [...current.path, [newX, newY]];
        queue.push({ x: newX, y: newY, path: newPath });
      }
    }
  }

  // 若棋盘内无法到达（理论上骑士能到达任意点，此情况一般不会出现）
  return "无法找到路径";
}

// 测试：起点(0,0)到终点(5,4)
console.log(knightsMove(0, 0, 5, 4));

原问题逐一修复说明 #

1. 路径追踪问题

   • 原代码未记录每个节点的来源路径，修复后队列中每个元素携带path数组，存储从起点到当前节点的完整坐标序列，到达终点时直接返回该数组即可。

2. 重复访问节点问题

   • 原代码用一维数组存储访问过的坐标，判断逻辑混乱，改为二维visited数组，直接通过visited[newX][newY]判断是否已访问，生成新坐标时先做此检查，避免重复入队。

3. 终点识别错误

   • 原代码用[currentX, currentY] === [endX, endY]做判断，这是数组引用比较（两个新数组永远不相等），修复后直接比较数值current.x === endX && current.y === endY，且在取出队列节点时立即检查，确保及时识别终点。

4. 循环执行与状态更新问题

   • 原代码初始队列赋值错误：queue.push(startX)返回的是队列长度，不是插入的元素值，导致currentX/currentY初始值错误；
   • 原边界判断逻辑错误：board[vectorX] == undefined无法正确判断坐标是否越界，改为直接检查newX/newY是否在0-7范围内；
   • 修复后循环逻辑基于BFS（广度优先）的标准流程，每次取出队列头部节点处理，正确更新visited标记和队列内容，确保遍历所有可能的最短路径节点。

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