Traversing a 2D Matrix using BFS

Question

I am hoping someone can help me. I am trying to implement a BFS on a 2D matrix using JavaScript.

The function has an input of a 2D matrix ("lot") that has cells of either 1 or 0. The traversal should look for its destination of the INT 9, and only able to traverse through the INT 1. It should not be able to traverse through 0s, or the visited cells that I am labeling as -1. Once it reaches its destination, it should return the number of moves that it took to find the destination. In the below example, it would be 3 because it would take 3 moves to get to 9 from the 0,0 position, aka the starting point.

I keep getting an out-of-bounds error, or just the wrong answer altogether. I've looked at this code so much, it would be really helpful to get someone else's perspective.

@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;
}

Nina Scholz Nina Scholz · Accepted Answer · 2021-01-31T09:05:07

I would change the structure of the queue and add the count as well at index zero.

Then I would change the check for the indices and the coming value to prevent viting visited cells again.

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));

Traversing a 2D Matrix using BFS

1 Answers