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

 class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:

        R = len(grid)
        C = len(grid[0])

        if grid[0][0] == 1 or grid[R-1][C-1] == 1:
            return -1

        if R==1 and C==1:
            return 1

        visited = set()
        q = deque()
        q.append((0, 0, 1))


        directions = [
            (0,1), (0,-1), (1,0), (-1, 0), 
            #(0,1), (0,-1), (1,0), (-1, 0), 
            (1,1), (1,-1), (-1,1), (-1,-1)
            #(1,1), (1,-1), (-1,1), (-1,1) 

        ]

        while q:
            r, c, d = q.popleft()

            for rr, cc in directions:
                nr = r + rr
                nc = c + cc

                if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in visited and grid[nr][nc]==0:
                    visited.add((nr, nc))
                    q.append((nr, nc, d+1))

                    if (nr, nc) == (R - 1, C - 1): 
                        return d + 1


        return -1