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

# 풀이 과정
"""
bfs 
"""
from collections import deque


def arround(x, y, check_x, check_y):
    check = [[(x + 1, y), (x - 1, y)], [(x, y + 1), (x, y - 1)]]

    for i in check:
        if (check_x, check_y) in i:
            continue
        else:
            d = i

    k = []

    for nx, ny in d:
        if nx != x:
            k.append((nx, ny, nx, check_y))
        elif ny != y:
            k.append((nx, ny, check_x, ny))

    return k


def solution(board):
    m = len(board)
    n = len(board[0])
    # 이동
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    # 회전8,이동4

    robot = ((0, 0), (0, 1))

    q = deque([((0, 0), (0, 1), 0)])

    visit = set([])

    result = float("inf")

    while q:
        z = q.popleft()

        if (m - 1, n - 1) in z:
            result = min(result, z[2])
            continue

        x1, x2 = z[0][0], z[0][1]
        y1, y2 = z[1][0], z[1][1]
        count = z[2]

        if not ((z[0]), (z[1])) in visit or not ((z[1]), (z[0])) in visit:
            visit.add(((z[0]), (z[1])))
            visit.add(((z[1]), (z[0])))

        else:
            continue

        # 이동
        for nx, ny in zip(dx, dy):
            if 0 <= nx + x1 < m and 0 <= ny + x2 < n and 0 <= nx + y1 < m and 0 <= ny + y2 < n:
                if board[nx + x1][ny + x2] == 0 and board[nx + y1][ny + y2] == 0 and not ((nx + x1, ny + x2), (
                nx + y1, ny + y2)) in visit and not ((nx + y1, ny + y2), (nx + x1, ny + x2)) in visit:
                    q.append(((nx + x1, ny + x2), (nx + y1, ny + y2), count + 1))
                    # visit.add(((nx+x1,ny+x2),(nx+y1,ny+y2)))
                    # visit.add(((nx+y1,ny+y2),(nx+x1,ny+x2)))

        check = arround(x1, x2, y1, y2)

        for nx, ny, mx, my in check:
            if 0 <= nx < m and 0 <= ny < n:
                if board[nx][ny] == 0 and board[mx][my] == 0 and not ((nx, ny), (x1, x2)) in visit and not ((nx, ny), (
                x1, x2)) in visit:
                    q.append(((x1, x2), (nx, ny), count + 1))
                    # visit.add(((x1,x2),(nx,ny)))
                    # visit.add(((nx,ny),(x1,x2)))

        check = arround(y1, y2, x1, x2)

        for nx, ny, mx, my in check:
            if 0 <= nx < m and 0 <= ny < n:
                if board[nx][ny] == 0 and board[mx][my] == 0 and not ((nx, ny), (y1, y2)) in visit and not ((nx, ny), (
                y1, y2)) in visit:
                    q.append(((y1, y2), (nx, ny), count + 1))
                    # visit.add(((y1,y2),(nx,ny)))
                    # visit.add(((nx,ny),(y1,y2)))
    return result