Given an n x n grid of 0s and 1s, return the length of the shortest clear path from the top-left cell to the bottom-right cell, or -1 if none exists. A clear path visits only cells with value 0, and consecutive cells must touch by an edge or a corner (8 directions). The length is the number of cells visited, including both ends.
- n == grid.length == grid[i].length
- 1 <= n <= 100
- grid[i][j] is 0 or 1
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
DFS over all paths is exponential and does not naturally give the shortest one. Since each move has equal cost, BFS visits cells in order of distance from the start, so the first time we reach the bottom-right cell we have the answer. We mark cells as visited when we enqueue them to avoid adding the same cell twice. The only twist versus a normal grid BFS is the 8 neighbours.
Algorithm
- If
grid[0][0]orgrid[n-1][n-1]is 1, return -1. - Push
(0, 0)with length 1 and mark it visited. - Pop a cell; if it is the bottom-right cell, return its length.
- For each of the 8 neighbours inside the grid that is 0 and unvisited, mark it and push it with length + 1.
- If the queue empties, return -1.
O(n^2)Space: O(n^2)class Solution: def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: n = len(grid) if grid[0][0] == 1 or grid[n - 1][n - 1] == 1: return -1 dist = [[0] * n for _ in range(n)] # 0 = unvisited dist[0][0] = 1 q = deque([(0, 0)]) while q: r, c = q.popleft() if r == n - 1 and c == n - 1: return dist[r][c] for dr in (-1, 0, 1): for dc in (-1, 0, 1): nr, nc = r + dr, c + dc if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and dist[nr][nc] == 0: dist[nr][nc] = dist[r][c] + 1 # mark when pushed q.append((nr, nc)) return -1