在二维数组中寻找最短路径（Javascript） [英] Finding shortest path in two dimensional array (Javascript)

问题描述

我正在尝试实现一种算法，该算法在以下二维数组中找到最短路径（从左上角到右下角）：

I am trying to implement an algorithm, that finds the shortest path in the following two dimensional array (from the top left corner, to the right bottom corner):

      [ [ 'A', 'A', 'A', 'B', 'A' ],
        [ 'B', 'B', 'B', 'B', 'B' ],
        [ 'A', 'B', 'A', 'A', 'A' ],
        [ 'A', 'B', 'B', 'B', 'B' ],
        [ 'A', 'A', 'A', 'A', 'A' ] ]

规则是，路径必须在A和B之间交替。

The rules are, that the path must alternate between A's and B's.

输出必须是number指定通过数组所需的最小步骤数。 （在示例中，预期输出为13）

The output must be a number specifying the smallest number of steps it will take to go through the array. (In the example the expected output is 13)

是否有人知道可以帮助我解决此问题的简单图形实现？

Does anyone know of a simple Graph implementation that can help me solve this problem?

推荐答案

由于它代表无向 未加权图形，您只需使用BFS：

Since it represents an undirected unweighted graph, you can simply use BFS:

const m =
  [ [ 'A', 'A', 'A', 'B', 'A' ],
    [ 'B', 'B', 'B', 'B', 'B' ],
    [ 'A', 'B', 'A', 'A', 'A' ],
    [ 'A', 'B', 'B', 'B', 'B' ],
    [ 'A', 'A', 'A', 'A', 'A' ] ]

let successors = (root, m) => {
  let connectedCells = [
    [root[0] - 1, root[1]],
    [root[0], root[1] - 1],
    [root[0] + 1, root[1]],
    [root[0], root[1] + 1]
  ]

  const validCells = connectedCells.filter(
    (cell) => (
      cell[0] >= 0 && cell[0] < m.length 
      && cell[1] >= 0 && cell[1] < m[0].length)
  )

  const successors = validCells.filter(
    (cell) => (m[cell[0]][cell[1]] !== m[root[0]][root[1]])
  )

  return successors
}

const buildPath = (traversalTree, to) => {
  let path = [to]
  let parent = traversalTree[to]
  while (parent) {
    path.push(parent)
    parent = traversalTree[parent]
  }
  return path.reverse()
}

const bfs = (from, to) => {
  let traversalTree = []
  let visited = new Set
  let queue = []
  queue.push(from)

  while (queue.length) {
    let subtreeRoot = queue.shift()
    visited.add(subtreeRoot.toString())

    if (subtreeRoot.toString() == to.toString()) return buildPath(traversalTree, to)

    for (child of successors(subtreeRoot, m)) {
      if (!visited.has(child.toString())){
        traversalTree[child] = subtreeRoot
        queue.push(child)
      }
    }
  }
}


console.log(bfs([0,0], [4,4]).length) // => 13

这篇关于在二维数组中寻找最短路径（Javascript）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！