BFS with 8 directions. Return length when reaching destination.
function shortestPathBinaryMatrix(grid): n = len(grid) if grid[0][0] == 1 or grid[n-1][n-1] == 1: return -1 queue = [(0, 0, 1)] grid[0][0] = 1 dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] while queue: r, c, length = queue.pop(0) if r == n - 1 and c == n - 1: return length for dr, dc in dirs: nr, nc = r + dr, c + dc if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0: grid[nr][nc] = 1 queue.append((nr, nc, length + 1)) return -1
time and space.