"""
출처:프로그래머스,
https://school.programmers.co.kr/learn/courses/30/lessons/1844
"""

#풀이과정


from collections import deque


def solution(maps):
    q = deque([[0, 0, 1]])

    visit = [[False] * len(maps[0]) for _ in range(len(maps))]

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    while q:
        x, y, z = q.popleft()

        visit[x][y] = True

        for new_x, new_y in zip(dx, dy):
            if 0 <= x + new_x < len(maps) and 0 <= y + new_y < len(maps[0]) and visit[x + new_x][y + new_y] == False and \
                    maps[x + new_x][y + new_y] != 0:
                q.append([x + new_x, y + new_y, z + 1])
                visit[x + new_x][y + new_y] = True

        if visit[len(maps) - 1][len(maps[0]) - 1] == True:
            return z + 1

    return -1