Как реализовать поиск кратчайшего пути по двоичной двумерной матрице (JS)?

Question

Допустим, что карта представлена как двумерная матрица 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],
]

Answer 1

Решение на основе волнового алгоритма (генерация поля досягаемости от стартовой точки в шагах, с последующей обратной трассировкой по достижении целевой точки):

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())
})

БЛОГ НА HUSL

Как реализовать поиск кратчайшего пути по двоичной двумерной матрице (JS)?

Ответы (1 шт):