> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/08_bfs/1091.-shortest-path-in-binary-matrix.md).

# 1091. Shortest Path in Binary Matrix

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

## solution

```python
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

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

```python
# 用hashmap存上一步的坐标

```