DEV Community

Abhishek Chaudhary
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:
                    visited.add((i, j))
                    path.append((i, j, d + 1))
        return -1
Enter fullscreen mode Exit fullscreen mode

Top comments (0)