In grid BFS, nodes are coordinate pairs . Here is the pattern:
function shortestPathBinaryMatrix(grid):
n = grid.size
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
dist = 2D array of size n x n, all -1
dist[0][0] = 1
q = queue with (0, 0)
directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
while q is not empty:
(r, c) = q.pop()
if r == n - 1 and c == n - 1:
return dist[r][c]
for (dr, dc) in directions:
nr = r + dr
nc = c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
q.push((nr, nc))
return -1
This runs in time and uses space.