1
from collections import deque
2

3
def shortest_path(grid):
4
    m, n = len(grid), len(grid[0])
5
    q = deque([(0, 0, 0)])
6
    seen = {(0, 0)}
7
    dirs = [(1,0), (-1,0), (0,1), (0,-1)]
8
    while q:
9
        x, y, d = q.popleft()
10
        if (x, y) == (m - 1, n - 1):
11
            return d
12
        for dx, dy in dirs:
13
            nx, ny = x + dx, y + dy
14
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0 and (nx, ny) not in seen:
15
                seen.add((nx, ny))
16
                q.append((nx, ny, d + 1))
17
    return -1