1091. Shortest Path in Binary Matrix

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

solution

class Solution:
    def __init__(self):
        self.dirs = [[0, 1], [1, 0], [0, -1], [-1, 0], [1, 1], [-1, -1], [1, -1], [-1, 1]]

    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] != 0 or grid[-1][-1] != 0:
            return -1

        m = len(grid)
        n = len(grid[0])

        start = (0, 0)
        target = (m - 1, n -1)

        queue = collections.deque([start])
        # 别忘了标记visited, 否则超时
        # 注意二维bfs中，list是unhashable的, 因此用dict类似hash set. 或者和岛屿问题一样通过改变数字实现
        visited = {start}  # 或 visited = set((0, 0)), 即使是set中也要用tuple, list is unhashable
        res = 0

        while queue:
            res += 1
            for _ in range(len(queue)):
                x, y = queue.popleft()
                if (x, y) == target:
                    return res

                for dx, dy in self.dirs:
                    new_x = x + dx
                    new_y = y + dy
                    if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == 0 and (new_x, new_y) not in visited:
                        queue.append([new_x, new_y])
                        visited.add((new_x, new_y))
        return -1

时间复杂度：O(mn) 空间复杂度：O(mn)

follow up

• 输出路径 (全部或其中一个)

# 用hashmap存上一步的坐标