BFS算法2D网格图邻接节点查找返回NaN问题求助

现有代码核心错误 #

getNeighbours 函数问题 #

• left、right 变量声明后未赋值，值为undefined，用 undefined 作为数组索引赋值，无法得到有效结果
• 仅处理了行维度的单边判断，没有覆盖所有上下邻接场景，也完全未处理列维度的左右邻接节点，同时没有做边界校验防止数组越界
• 没有返回neighbours数组，函数执行后无有效返回值
• 逻辑错误：非边界行应该同时存在上下两个邻接节点，用else if判断会导致中间行只能获取单个邻接节点

createGrid 函数问题 #

• 循环起始值从1开始，导致grid[0]为空，网格索引整体错位
• 内部循环中每次将createNode的返回值重新赋值给整个grid变量，会覆盖原有网格结构
• 每行循环结束后重复 push 已存在的grid[row]，导致数组结构混乱

修正后代码 #

修正后的 createGrid #

const createGrid = () => {
  const grid = [];
  // 行从0开始，共20行
  for (let row = 0; row < 20; row++) {
    grid[row] = [];
    // 列从0开始，共47列
    for (let col = 0; col < 47; col++) {
      // 直接给对应位置赋值节点，不覆盖整个grid
      grid[row][col] = createNode(grid, row, col);
    }
  }
  return grid;
};

修正后的 getNeighbours #

const getNeighbours = (row, col, grid) => {
  const neighbours = [];
  const rowCount = grid.length;
  const colCount = grid[0].length;
  // 添加上邻居
  if (row > 0) {
    neighbours.push(grid[row - 1][col]);
  }
  // 添加下邻居
  if (row < rowCount - 1) {
    neighbours.push(grid[row + 1][col]);
  }
  // 添加左邻居
  if (col > 0) {
    neighbours.push(grid[row][col - 1]);
  }
  // 添加右邻居
  if (col < colCount - 1) {
    neighbours.push(grid[row][col + 1]);
  }
  return neighbours;
};

调用说明 #

• 调用getNeighbours时需要传入当前节点的行、列，以及已生成的grid实例，即可得到该节点所有有效的四方向邻接节点
• 如果需要八方向邻接，额外增加四个斜角方向的边界判断即可

内容的提问来源于stack exchange，提问作者Ben.Clough