LeetCode Shortest Path in Binary Matrix Solution
Given an n x n
binary matrix grid
, return the length of the shortest clear path in the matrix. If there is no clear path, return -1
.
A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)
) to the bottom-right cell (i.e., (n - 1, n - 1)
) such that:
- All the visited cells of the path are
0
. - All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.
Example 1:
Input: grid = [[0,1],[1,0]]
Output: 2
Example 2:
Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Example 3:
Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1
Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1
Problem Link: https://leetcode.com/problems/shortest-path-in-binary-matrix/
Solution
To find the shortest clear path from (0,0) to (n-1, n-1), we will perform breadth first search from (0,0).
First, we need to make sure that grid[0][0]
is 0
, otherwise a clear path does not exist.
Each cell has (at most) 8 neighbours, and we can use the get_neighbours
function to find the neighbours.
Then, we will only continue on cells labeled 0
, the number of levels of the BFS traversal is the length of the shortest clear path.
Implementation
1def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
2 if grid[0][0] == 1: return -1
3
4 n = len(grid)
5 dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
6 def get_neighbours(x, y):
7 neighbours = []
8 for dx, dy in dirs:
9 if 0 <= x+dx < n and 0 <= y+dy < n:
10 neighbours.append((x+dx, y+dy))
11 return neighbours
12
13 length = 1
14 q = deque()
15 q.append((0,0))
16 unvisited = [[True for _ in range(n)] for _ in range(n)]
17 unvisited[0][0] = False
18 while q:
19 count = len(q)
20 for _ in range(count):
21 x, y = q.popleft()
22 if x == n -1 and y == n-1:
23 return length
24 for nx, ny in get_neighbours(x, y):
25 if grid[nx][ny] == 0 and unvisited[nx][ny]:
26 q.append((nx, ny))
27 unvisited[nx][ny] = False
28 length += 1
29 return -1