带障碍物的网格地图中点间距离计算方法问询

无障碍物场景：曼哈顿距离 #

当网格中没有障碍物时，两点间的步数距离可以直接用曼哈顿距离计算，即两点行列数差值的绝对值之和：

const grid = [
  [1, 1, 1, 1],
  [1, 1, 1, 1],
  [1, 1, 1, 1],
  [1, 1, 1, 1],
];
const point1 = [0, 3];
const point2 = [3, 2];
const distance12 = Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]); // 结果为4

有障碍物场景：曼哈顿距离失效 #

当网格存在障碍物（0表示障碍物，1表示可行单元格）时，曼哈顿距离不再适用，需要寻找实际可通行的最短路径。比如下面的示例，从[0,3]到[3,2]的实际步数为8：

const grid = [
  [1, 1, 1, 1],
  [1, 1, 1, 1],
  [1, 0, 0, 0],
  [1, 1, 1, 1],
];
const point1 = [0, 3];
const point2 = [3, 2];
// 实际最短路径步数为8

可行解决方案：广度优先搜索（BFS） #

洪水填充算法失效通常是因为未正确处理已访问单元格，导致重复遍历或逻辑错误。BFS是解决这类网格最短路径问题的标准方案，它按层级遍历单元格，保证首次到达目标点时的步数就是最短路径长度。

BFS实现代码 #

function calculateShortestDistance(grid, start, end) {
  // 网格边界判断
  const rows = grid.length;
  const cols = grid[0].length;
  if (rows === 0 || cols === 0) return -1;
  if (start[0] === end[0] && start[1] === end[1]) return 0;

  // 上下左右四个移动方向
  const directions = [[-1,0], [1,0], [0,-1], [0,1]];
  // 记录已访问单元格，避免重复遍历
  const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
  // 队列存储[行坐标, 列坐标, 当前步数]
  const queue = [[start[0], start[1], 0]];
  visited[start[0]][start[1]] = true;

  while (queue.length > 0) {
    const [row, col, steps] = queue.shift();

    // 遍历四个相邻方向
    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;

      // 判断新位置是否合法：在网格内、可行走、未访问
      if (newRow >= 0 && newRow < rows && newCol >=0 && newCol < cols) {
        // 到达目标点，返回当前步数+1
        if (newRow === end[0] && newCol === end[1]) {
          return steps + 1;
        }
        if (grid[newRow][newCol] === 1 && !visited[newRow][newCol]) {
          visited[newRow][newCol] = true;
          queue.push([newRow, newCol, steps + 1]);
        }
      }
    }
  }

  // 无法到达目标点时返回-1
  return -1;
}

// 测试示例
const grid = [
  [1, 1, 1, 1],
  [1, 1, 1, 1],
  [1, 0, 0, 0],
  [1, 1, 1, 1],
];
const point1 = [0, 3];
const point2 = [3, 2];
console.log(calculateShortestDistance(grid, point1, point2)); // 输出8

为什么BFS有效？ #

BFS从起点开始逐层探索所有可到达的单元格，每一层对应步数加1。由于优先遍历近的单元格，首次到达目标点时的步数必然是最短路径的长度，不会出现绕路情况。

优化方案：双向BFS #

如果网格规模较大，双向BFS可以大幅减少遍历的单元格数量：同时从起点和终点开始搜索，当两个搜索队列的单元格相遇时，将两边的步数相加就是最短路径总长度。

内容的提问来源于stack exchange，提问作者L.P.