1091.md

1091. Shortest Path in Binary Matrix

Solution 1 (time O(n^2), space O(n^2))

# BFS
class Solution(object):
    def shortestPathBinaryMatrix(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)
        if grid[0][0] == 1:
            return -1
        q = deque()
        vis = set()
        q.append((0, 0, 1))
        vis.add((0, 0))
        while q:
            cur_x, cur_y, cur_step = q.popleft()
            if cur_x == n - 1 and cur_y == n - 1:
                return cur_step
            for dx, dy in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]:
                new_x = cur_x + dx
                new_y = cur_y + dy
                if not (0 <= new_x < n and 0 <= new_y < n):
                    continue
                if grid[new_x][new_y] == 1:
                    continue
                if (new_x, new_y) in vis:
                    continue
                q.append((new_x, new_y, cur_step + 1))
                vis.add((new_x, new_y))
        return -1