Leetcode 1171 Solution

This article provides solution to leetcode question 1171 (shortest-path-in-binary-matrix)
Categories:
Tags:
Access this page by simply typing in "lcs 1171" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/shortest-path-in-binary-matrix

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