JS迷宫求解算法迭代逻辑未覆盖特殊场景问题求助

问题原因 #

该逻辑失效通常是两个原因导致：

• 仅做了单次重合判定，未做循环校验，若多次随机生成的终点都落在起点位置就会跳过重新生成逻辑
• 重合判定条件写得不准确，比如坐标对比写反、仅对比了单个坐标值

优化方案 #

采用循环生成终点的逻辑，直到生成的终点满足「不与起点重合、落在可通行区域」两个条件为止，参考实现：

const ROW_COUNT = maze.length;
const COL_COUNT = maze[0].length;
let endX, endY;
// 起点固定为(0,0)，循环直到生成合法终点
do {
  endX = Math.floor(Math.random() * ROW_COUNT);
  endY = Math.floor(Math.random() * COL_COUNT);
} while (
  // 不能是起点
  (endX === 0 && endY === 0) ||
  // 不能落在障碍物上
  maze[endX][endY] !== 'O'
);
// 写入终点标记
maze[endX][endY] = '^';

问题原因 #

你给出的示例迷宫存在至少一条从起点到终点的通路(0,0)→(0,1)→(0,2)→(0,3)→(0,4)，遍历提前终止和遍历方向无关，通常是以下几个常见错误导致：

• 未维护独立的已访问标记矩阵，错误地将已访问的可通行格子直接改为障碍物标记，导致其他路径无法通行
• 遍历方向覆盖不全，仅实现了向右、向下两个方向的检查，漏掉了向上、向左的合法路径
• 终点判定逻辑位置错误，仅在检查周边格子的时候判定终点，走到终点本身时反而没有触发终止逻辑
• DFS遍历未做回溯，走到死胡同时没有撤销已访问标记，后续正确路径无法走通

优化方案 #

建议改用BFS（广度优先遍历）实现求解，天生不存在DFS的回溯问题，参考实现：

function solveMaze(maze) {
  const ROW = maze.length;
  const COL = maze[0].length;
  // 四个遍历方向：上、下、左、右
  const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  // 已访问矩阵，避免重复遍历
  const visited = Array.from({ length: ROW }, () => Array(COL).fill(false));
  // 队列存储当前坐标和已走路径
  const queue = [[0, 0, []]];
  visited[0][0] = true;

  while (queue.length) {
    const [x, y, path] = queue.shift();
    // 找到终点，返回路径
    if (maze[x][y] === '^') return [...path, [x, y]];
    // 遍历四个方向
    for (const [dx, dy] of DIRS) {
      const nx = x + dx;
      const ny = y + dy;
      // 边界校验+未访问+可通行/是终点
      if (
        nx >= 0 && nx < ROW &&
        ny >= 0 && ny < COL &&
        !visited[nx][ny] &&
        (maze[nx][ny] === 'O' || maze[nx][ny] === '^')
      ) {
        visited[nx][ny] = true;
        queue.push([nx, ny, [...path, [x, y]]]);
      }
    }
  }
  // 无有效路径
  return null;
}

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