"""
Shortest Path In Binary Matrix

n an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, ..., C_k such that:

Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner)
C_1 is at location (0, 0) (ie. has value grid[0][0])
C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1])
If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).
Return the length of the shortest such clear path from top-left to bottom-right.  If such a path does not exist, return -1.

 

Example 1:

Input: [[0,1],[1,0]]


Output: 2

Example 2:

Input: [[0,0,0],[1,1,0],[1,1,0]]


Output: 4

 

Note:

1 <= grid.length == grid[0].length <= 100
grid[r][c] is 0 or 1
"""

"""
BFS

Time: O(N)
Space: O(N)
"""
class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        directions = [(1, 1), (1, 0), (-1, 0), (-1, 1), (-1, -1), (0, 1), (0, -1), (1, -1)]
        
        if not len(grid) or not len(grid[0]):
            return 0
        
        if grid[0][0] == 1:
            return -1
        n = len(grid)
        queue = collections.deque([(0, 0, 1)])
        visited = set()
        while queue:
            i, j, d = queue.popleft()
            if i == n - 1 and j == n - 1:
                return d
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 0:
                    grid[ni][nj] = 1
                    queue.append((ni, nj, d+1))
        return -1

