Why does this BFS shortest-path helper return one extra step for reachable cells?

programming web dev
1

I’m computing the shortest path in a grid with BFS, but reachable cells sometimes come back with a distance that’s 1 too high. I expected the bottom-right cell here to be 4 steps away, but my function returns 5. Am I incrementing distance in the wrong place?

function shortest(grid) {
  const q = [[0, 0, 0]];
  const seen = new Set(['0,0']);
  while (q.length) {
    const [r, c, d] = q.shift();
    if (r === grid.length - 1 && c === grid[0].length - 1) return d + 1;
    for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nr = r + dr, nc = c + dc;
      if (grid[nr]?.[nc] === 0 && !seen.has(`${nr},${nc}`)) q.push([nr, nc, d + 1]);
    }
  }
}

Grid is a 2D array where 0 means open and 1 means blocked.

WaffleFries

2

@WaffleFries your `return d + 1

is the extra step, because the queue already stores the distance after each move;
also add

seen.add(`${nr},${nc}`)` when you enqueue or you may visit the same cell more than once.

BobaMilk