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

# 풀이 과정
"""
조작횟수: enter+방향키

목표:남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값 

생각방향:
카드를 하나 고르면 무조건 그 짝을 무조건 찾아야한다
그 다음 카드를 선택하는 기준은?
배열 자체가 작기 때문에 크기가 중요하진 않다 모든 경우의 수 고려가능 
칸 16개이기 떄문에 카드 종류 최대 8개
뽑을 순서의 카드를 미리 정한 후 그 순서에 맞춰서 뽑은 후 순서 정하기


# 시간적으로 코드가 문제가 없으므로 논리의 틀린 부분이 없기에 수정 후 풀이가능
만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다. < 중요한 생각의 포인트 기점

"""

import copy
from itertools import combinations
from itertools import permutations
from collections import defaultdict
from collections import deque


# 두 점 사이의 이동 (현재 위치, 이동할 위치, 이동 횟수, 해당 게임판)
def start(now_x, now_y, nex_x, nex_y, fir):
    """
    if now_x==nex_x and now_y==nex_y: return 0

    queue, visit = deque([[now_x, now_y, 0]]), {(now_x,now_y)}
    while queue:                    # BFS
        x, y, c = queue.popleft()
        for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
            nx, ny = x+dx, y+dy     # Normal move
            cx, cy = x, y
            while True:             # Ctrl + move
                cx, cy = cx+dx, cy+dy
                if not (0 <= cx <= 3 and 0 <= cy <= 3):
                    cx, cy = cx-dx, cy-dy
                    break
                elif fir[cx][cy] != 0:
                    break

            if (nx, ny) == (nex_x,nex_y) or (cx, cy) == (nex_x,nex_y):  # 도착 최단 경로
                return c+1

            if (0 <= nx <= 3 and 0 <= ny <= 3) and (nx, ny) not in visit:
                queue.append((nx, ny, c+1))
                visit.add((nx, ny))
            if (cx, cy) not in visit:
                queue.append((cx, cy, c+1))
                visit.add((cx, cy))

    """
    q = deque([[now_x, now_y, count]])
    num = float("inf")
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    visit = set([])
    q = deque([(now_x, now_y, 0)])
    while q:
        i, j, c = q.popleft()

        # 방문 기록
        visit = visit | set([(i, j)])

        if i == nex_x and j == nex_y:
            return c

        for nx, ny in zip(dx, dy):

            x, y = i, j

            if 0 <= x + nx < 4 and 0 <= y + ny < 4:
                if not (x + nx, y + ny) in visit:
                    q.append((x + nx, y + ny, c + 1))
                    visit = visit | set([(x + nx, y + ny)])

            ctrlx, ctrly = i, j

            while True:
                ctrlx += nx
                ctrly += ny

                if not 0 < ctrlx < 4 or not 0 < ctrly < 4:
                    if nx == 1:
                        if not (3, ctrly) in visit:
                            q.append((3, ctrly, c + 1))
                            visit = visit | set([(3, ctrly)])
                    elif nx == -1:
                        if not (0, ctrly) in visit:
                            q.append((0, ctrly, c + 1))
                            visit = visit | set([(0, ctrly)])

                    elif ny == 1:
                        if not (ctrlx, 3) in visit:
                            q.append((ctrlx, 3, c + 1))
                            visit = visit | set([(ctrlx, 3)])
                    elif ny == -1:
                        if not (ctrlx, 0) in visit:
                            q.append((ctrlx, 0, c + 1))
                            visit = visit | set([(ctrlx, 0)])
                    break

                elif fir[ctrlx][ctrly] == 1:
                    if not (ctrlx, ctrly) in visit:
                        q.append((ctrlx, ctrly, c + 1))
                        visit = visit | set([(ctrlx, ctrly)])
                    break

    return 0


# k:카드 뽑는 순서, 게임판, 현 위치, 총 움직인 순서
def count(k, distance):
    order, game, location, count = k[0], k[1], k[2], k[3]
    x, y = location[0], location[1]
    result = float("inf")

    q = deque([[order, game, [x, y], count]])

    while q:
        new_order, new_game, new_location, new_count = q.popleft()
        new_x, new_y = new_location[0], new_location[1]

        new_order = deque(new_order)

        if len(new_order) == 0:
            # print(new_count,result)
            result = min(result, new_count)
            continue
        # print(new_order,"before")
        num = new_order.popleft()
        # print(new_order,"after")
        # one > two
        count_one = new_count
        # two > one
        count_two = new_count

        # 같은 카드는 2개이므로 어느쪽으로 갈지 택해야한다
        fir = copy.deepcopy(new_game)  # 새로운 게임판1
        fir_x, fir_y = distance[num][0]  # one 위치

        sec = copy.deepcopy(new_game)  # 새로운 게임판2
        sec_x, sec_y = distance[num][1]  # two 위치

        # location > one > two
        one = start(new_x, new_y, fir_x, fir_y, fir)
        count_one += (one + 1)
        one = start(fir_x, fir_y, sec_x, sec_y, fir)
        count_one += (one + 1)

        # fir 변형
        fir[fir_x][fir_y] = 0
        fir[sec_x][sec_y] = 0
        order_one = copy.deepcopy(new_order)
        q.append([order_one, fir, [sec_x, sec_y], count_one])

        # location > two > one
        two = start(new_x, new_y, sec_x, sec_y, sec)
        count_two += (two + 1)
        two = start(sec_x, sec_y, fir_x, fir_y, sec)
        count_two += (two + 1)

        # sec 변형
        sec[fir_x][fir_y] = 0
        sec[sec_x][sec_y] = 0
        order_two = copy.deepcopy(new_order)
        q.append([order_two, sec, [fir_x, fir_y], count_two])

        # if count_one>=count_two:
        #     q.append([order_one,fir,[sec_x,sec_y],count_one])
        # else:
        #     q.append([order_two,sec,[fir_x,fir_y],count_two])

    return result


def solution(board, r, c):
    result = float("inf")

    # 카드 위치
    distance = defaultdict(list)

    # 현재 위치
    d = [r, c]

    # 카드 종류
    card = []

    for i in range(4):
        for j in range(4):
            if board[i][j] != 0:
                card.append(board[i][j])

    card = list(set(card))

    for i in card:
        for v in range(4):
            for w in range(4):
                if board[v][w] == i:
                    distance[i].append([v, w])

    turn = list(permutations(card, len(card)))
    turn = list(map(list, turn))

    # print("turn",turn)

    q = []

    # 카드 뽑는 순서,게임판,현 위치, 총 움직인순서
    for i in turn:
        new = copy.deepcopy(board)
        q.append([i, new, [r, c], 0])

    while q:
        k = q.pop()
        check = count(k, distance)

        result = min(check, result)

    return result