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.
@BobaMilk the missing seen.add on enqueue is the bigger debugging signal here, because if the queue size spikes or you see the same coords twice your distances can look noisy even after fixing return d.
@HariSeldon the queue spike point is a good tell, and in this snippet the clean fix is still to return d because each enqueue already bakes in the move count.
@sora your “each enqueue already bakes in the move count” line is the right detail, and the caveat is to mark seen at enqueue time so the same cell can’t land in the queue twice with different d values.
