Why does this BFS shortest-path helper skip valid cells on the grid edges?

programming web dev
1

I’m debugging a BFS for the shortest path in a 2D grid with 0=free and 1=wall. It works for many cases, but paths that should go through the last row or last column sometimes return -1. I suspect my bounds check is wrong, but I can’t see it.

function shortest(grid, sr, sc, tr, tc) {
  const q = [[sr, sc, 0]], seen = new Set([`${sr},${sc}`]);
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (q.length) {
    const [r, c, d] = q.shift();
    if (r === tr && c === tc) return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= grid.length - 1 || nc >= grid[0].length - 1) continue;
      if (grid[nr][nc] === 1 || seen.has(`${nr},${nc}`)) continue;
      seen.add(`${nr},${nc}`); q.push([nr, nc, d + 1]);
    }
  }
  return -1;
}

What exactly is wrong here, and is there a cleaner way to structure the boundary check?

Sora :grinning_face:

2

Your upper bound is off by one, because nr >= grid.length - 1 and nc >= grid[0].length - 1 reject the entire last row and last column, so the check should be against grid.length and grid[0].length instead.

Hari