主页 / 问题 / 1430602
Accepted
Артём Ионаш
Asked:2022-07-18 01:05:54 +0800 CST2022-07-18 01:05:54 +0800 CST

如何实现在二进制二维矩阵（JS）中查找最短路径？

  • 772

假设地图表示为二维矩阵grid，其中1是障碍物，0是自由路径：

const grid = [
  [0, 0, 0, 0],
  [0, 1, 1, 0],
  [0, 1, 0, 0],
  [0, 1, 0, 0],
]

如何编写获取最短路径掩码的方法findShortestPath(grid, start, end)？

grid[0][0]从到的最短路径示例grid[2][2]：

const path = [
  [1, 1, 1, 1],
  [0, 0, 0, 1],
  [0, 0, 1, 1],
  [0, 0, 0, 0],
]
javascript алгоритм

1 个回答

  1. Best Answer

    基于wave算法的解决方案（从起点逐步生成到达场，到达目标点后进行回溯）：在此处输入图像描述 

    const getShortestPath = (grid, start, end) => {
  const isPassable = (point) => grid[point.c1] && grid[point.c1][point.c2] === 0

  const getNeighbors = (point) =>
    [
      { c1: point.c1 - 1, c2: point.c2 },
      { c1: point.c1 + 1, c2: point.c2 },
      { c1: point.c1, c2: point.c2 - 1 },
      { c1: point.c1, c2: point.c2 + 1 },
    ].filter(isPassable)

  const getBacktraceMask = (grid) => {
    const backtrace = grid.map((row) => row.map(() => 0))
    let step = end
    while (step.c1 !== start.c1 || step.c2 !== start.c2) {
      backtrace[step.c1][step.c2] = 1
      const neighbors = getNeighbors(step)
      const neighbor = neighbors.find(
        (neighbor) =>
          grid[neighbor.c1][neighbor.c2] === grid[step.c1][step.c2] - 1,
      )
      if (!neighbor) return undefined
      step = neighbor
    }
    backtrace[step.c1][step.c2] = 1
    return backtrace
  }

  const queue = [start]
  const distances = grid.map((row) => row.map(() => 0))
  distances[start.c1][start.c2] = 1

  const isEnd = ({ c1, c2 }) => c1 === end.c1 && c2 === end.c2
  for (const step of queue) {
    for (const neighbor of getNeighbors(step)) {
      if (distances[neighbor.c1][neighbor.c2] === 0) {
        distances[neighbor.c1][neighbor.c2] = distances[step.c1][step.c2] + 1
        if (isEnd(neighbor)) return getBacktraceMask(distances)

        queue.push(neighbor)
      }
    }
  }

  return undefined
}

const grid = [
  [0, 0, 0, 0],
  [0, 1, 1, 0],
  [0, 1, 0, 0],
  [0, 1, 0, 0],
]
console.log({
  path: getShortestPath(grid, { c1: 0, c2: 0 }, { c1: 2, c2: 2 })
    .map((row) => row.join())
})

    • 0

相关问题