使用 BFS 遍历二维矩阵

Question

我希望有人能帮助我。我正在尝试使用 JavaScript.

在二维矩阵上实现 BFS

该函数有一个二维矩阵（“lot”）的输入，其单元格为 1 或 0。遍历应该寻找其 INT 9 的目的地，并且只能遍历 INT 1。它不应该能够遍历 0，或者我标记为 -1 的已访问单元格。一旦到达目的地，它应该 return 找到目的地所花费的移动次数。在下面的示例中，它将是 3，因为需要 3 次移动才能从 0,0 位置（即起点）到达 9。

我总是收到越界错误，或者完全是错误的答案。我看了这么多代码，了解别人的观点真的很有帮助。

@input
let lot = [
          [1, 0, 0],
          [1, 0, 0],
          [1, 9, 0]
          ];

function distanceTraversed(lot) {
  let queue = [[0,0]];
  let count = 0;

  while (queue.length > 0) {
    let directions = queue.shift();
    let i = directions[0];
    let j = directions[1];
    
    if (lot[i][j] === 9) {
      return count;
    }
    //moving up
    if (i > 0 && lot[i][j] > 0) {
      queue.push([i - 1, j]);
    }

    //moving down
    if (i <= lot.length && lot[i][j] > 0) {
      queue.push([i + 1, j]);
    }

    //moving left
    if (j > 0 && lot[i][j] > 0) {
      queue.push([i, j - 1]);
    }

    //moving right
    if (j <= lot[i].length && lot[i][j] > 0) {
      queue.push([i, j + 1]);
    }

    //setting visited cells
    lot[i][j] = -1;
  }
  count++
  return -1;
}

Answer 1

我会更改 queue 的结构并在索引零处添加计数。

然后我会更改对索引和即将到来的值的检查，以防止再次访问已访问的单元格。

function distanceTraversed(lot) {
    const queue = [[0, 0, 0]];

    while (queue.length) {
        let [count, i, j] = queue.shift();

        if (lot[i][j] === 9) return count;
        if (lot[i][j] === -1) continue;

        //setting visited cells
        lot[i][j] = -1;

        //moving up
        if (i > 0 && lot[i - 1][j] !== -1) queue.push([count + 1, i - 1, j]);

        //moving down
        if (i + 1 < lot.length && lot[i + 1][j] !== -1) queue.push([count + 1, i + 1, j]);
    
        //moving left
        if (j > 0 && lot[i][j - 1] !== -1) queue.push([count + 1, i, j - 1]);

        //moving right
        if (j + 1 < lot[i].length && lot[i][j + 1] !== -1) queue.push([count + 1, i, j + 1]);
    }
    return -1;
}

let lot = [[1, 0, 0], [1, 0, 0], [1, 9, 0]];

console.log(distanceTraversed(lot));

使用 BFS 遍历二维矩阵

Traversing a 2D Matrix using BFS

javascript

graph

breadth-first-search

matrix

shortest-path