[link](https://leetcode.com/problems/shortest-path-in-binary-matrix/description/)

---

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

---

The variable N is assigned the length of the grid, assuming it is a square matrix. The code checks if the top-left and bottom-right cells are obstacles (equal to 1). If either of them is an obstacle, it is not possible to reach the bottom-right cell, so the function returns -1.

The q deque is used to store the coordinates of cells to visit during the breadth-first search. The top-left cell (0, 0) is added to the q deque and marked as visited in the visit set. The direction list represents the eight possible directions of movement: right, bottom-right, bottom, bottom-left, left, top-left, top, and top-right.

The distance variable is initialized to 1, which will store the minimum distance required to reach the bottom-right cell. The breadth-first search starts with a while loop that continues until the q deque is empty. In each iteration, the current layer of cells in the q deque is processed. For each cell, its neighboring cells are checked.

If a neighboring cell is out of bounds or an obstacle (equal to 1), it is skipped. If a neighboring cell is the bottom-right cell (N - 1, N - 1), the minimum distance required to reach it is returned. If a neighboring cell is valid (within bounds, not an obstacle, and not visited), it is marked as visited and added to the q deque.

After processing all cells in the current layer, the distance is incremented by 1. If the q deque is empty and the bottom-right cell has not been reached, it means it is not possible to reach the bottom-right cell. The function returns -1.

#### Solution 1

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        N = len(grid)
        
        if grid[0][0] != 0 or grid[N-1][N-1] != 0:
            return -1

        q = collections.deque()
        q.append((0, 0, 1))
        visit = set((0, 0))
        direction = [[0, 1], [1, 1], [1, 0], [1, -1], 
                     [0, -1], [-1, -1], [-1 ,0], [-1 ,1]]

        while q:
            r, c, length = q.popleft()
            if r == N - 1 and c == N - 1:
                return length
            
            for dr, dc in direction:
                row = r + dr
                col = c + dc
                if (min(row, col) < 0 or
                    row == N or col == N or
                    grid[row][col] == 1 or
                    (row, col) in visit):
                    continue
                visit.add((row, col))
                q.append((row, col, length + 1))
            
        return -1
        

O(T): O(n^2)
O(S): O(n^2)

---

Separate variable of length (distance) version

#### Solution 2

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        N = len(grid)
        
        if grid[0][0] != 0 or grid[N-1][N-1] != 0:
            return -1

        q = collections.deque()
        q.append((0, 0))
        visit = set((0, 0))
        direction = [[0, 1], [1, 1], [1, 0], [1, -1], 
                     [0, -1], [-1, -1], [-1 ,0], [-1 ,1]]

        distance = 1
        while q:
            for _ in range(len(q)):
                r, c = q.popleft()
                if r == N - 1 and c == N - 1:
                    return distance

                for dr, dc in direction:
                    row = r + dr
                    col = c + dc
                    if (min(row, col) < 0 or
                        row == N or col == N or
                        grid[row][col] == 1 or
                        (row, col) in visit):
                        continue
                    visit.add((row, col))
                    q.append((row, col))

            distance += 1
            
        return -1
        

O(T): O(n^2)
O(S): O(n^2)