# 1091. 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 (ie. 0,0) to the bottom-right cell (ie. n - 1, n - 1) such thatyt - all the visited cells are of the path 0 - all the adjacent cells of the path are 8-directionally connected (ie. they are different and they share an edge of a corner) the length of a clear path is the number of visited cells of this path """ class Solution(object): def shortestPathBinaryMatrix(self, grid): """ :type grid: List[List[int]] :rtype: int """ n = len(grid) if grid[0][0] or grid[n - 1][n - 1]: return -1 q = [(0, 0, 1)] grid[0][0] = 1 for i, j, d in q: if i == n - 1 and j == n - 1: return d for x, y in ( (i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1), ): if 0 <= x < n and 0 <= y < n and not grid[x][y]: grid[x][y] = 1 q.append((x, y, d + 1)) return -1 if __name__ == "__main__": obj = Solution() print(obj.shortestPathBinaryMatrix(grid=[[0, 1], [1, 0]])) print(obj.shortestPathBinaryMatrix(grid=[[0, 0, 0], [1, 1, 0], [1, 1, 0]])) print(obj.shortestPathBinaryMatrix(grid=[[1, 0, 0], [1, 1, 0], [1, 1, 0]]))