1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
from collections import deque


def next_step(maps, p):
    nexts = deque()
    n = len(maps) # row size
    m = len(maps[0]) # col size

    # (down, right, up, left)
    for t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        if 0 <= p[0] + t[0] < n and 0 <= p[1] + t[1] < m:
            if maps[p[0]+t[0]][p[1]+t[1]] == 1:
                nexts.append((p[0]+t[0], p[1]+t[1]))

    return nexts


def solution(maps):
    answer = -1
    n = len(maps)
    m = len(maps[0])

    end = (n-1, m-1)
    begin = (0, 0)
    maps[0][0] = 0
    begin_item = [begin, 1] # [point, cnt]

    q = deque([begin_item])
    while q:
        current, cnt = q.popleft()

        if current == end:
            return cnt

        nxts = next_step(maps, current)
        for nxt in nxts:
            q.append([nxt, cnt+1])
            maps[nxt[0]][nxt[1]] = 0

    return answer