1091. Shortest Path in Binary Matrix

[mengyushi]

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        '''
        Shortest Path: BFS
        when searched 0->1
        '''

        # if start/end point blocked
        if grid[0][0] or grid[-1][-1]:
            return -1

        M, N = len(grid), len(grid[0])

        q = [(0,0,1)]

        for i,j,d in q:

            if i == M -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<M and 0<=y<N and grid[x][y] == 0:
                    q.append((x,y,d+1))
                    grid[x][y] = 1

        return -1