## DEV Community

Abhishek Chaudhary

Posted on

# Shortest Path in Binary Matrix

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: