Leetcode 1171 Solution

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

        q = collections.deque()
        s = set()

        if grid[0][0] == 1:
            return -1

        q.append((0, 0))
        s.add((0, 0))

        k = 0
        while q:
            k += 1

            size = len(q)
            for _ in range(size):
                i, j = q.popleft()
                if i == N - 1 and j == N - 1:
                    return k

                for di, dj in [
                        (-1, 0),
                        (1, 0),
                        (0, -1),
                        (0, 1),
                        (1, 1),
                        (1, -1),
                        (-1, 1),
                        (-1, -1),
                ]:
                    next_i = i + di
                    next_j = j + dj

                    if not (0 <= next_i < N and 0 <= next_j < N):
                        continue

                    if (next_i, next_j) in s:
                        continue

                    if grid[next_i][next_j]:
                        continue

                    q.append((next_i, next_j))
                    s.add((next_i, next_j))

        return -1