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
SOLUTION:
from collections import deque
class Solution:
def neighbours(self, a, b, m, n):
for i in range(a - 1, a + 2):
for j in range(b - 1, b + 2):
if (i, j) != (a, b) and 0 <= i < m and 0 <= j < n:
yield (i, j)
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
if grid[0][0] != 0 or grid[-1][-1] != 0:
return -1
path = deque([(0, 0, 1)])
visited = {(0, 0)}
while len(path) > 0:
a, b, d = path.popleft()
if (a, b) == (m - 1, n - 1):
return d
for i, j in self.neighbours(a, b, m, n):
if grid[i][j] == 0 and (i, j) not in visited:
visited.add((i, j))
path.append((i, j, d + 1))
return -1
Top comments (0)