Given a matrix of 0s and 1s, we’re asked to start from grid[0][0] and make our way to grid[n-1][n-1] with the shortest path possible. This can be done using breadth-first search. We use the grid to keep track of the distance we’ve seen so far, which also helps us mark a location as seen.
The solution is as follows:
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
if grid[0][0] != 0 or grid[-1][-1] != 0:
return -1
n = len(grid)
directions = [
(-1, -1),
(-1, 0),
(-1, 1),
(0, -1),
(0, 1),
(1, -1),
(1, 0),
(1, 1),
]
def get_neighbours(row: int, col: int) -> tuple:
for i_diff, j_diff in directions:
i, j = row + i_diff, col + j_diff
if -1 < i < n and -1 < j < n and grid[i][j] == 0:
yield (i, j)
queue = []
queue.append((0, 0))
grid[0][0] = 1
while queue:
curr_queue, queue = queue, []
for row, col in curr_queue:
distance = grid[row][col]
if (row, col) == (n - 1, n - 1):
return distance
for i, j in get_neighbours(row, col):
grid[i][j] = distance + 1
queue.append((i, j))
return -1_ Time Complexity:
O(m) - We iterate through the edges to perform union_set.
_ Space Complexity:
O(n) - We track the parents and ranks of each node.