import java.awt.Point;
import java.util.Arrays;
import java.util.PriorityQueue;
class Route{
    int u, v, cost;
    public Route(int u, int v, int cost) {
        this.u = u;
        this.v = v;
        this.cost = cost;
    }
}
public class Solution {
    static int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    static boolean pictures[] = new boolean[8];
    public static int solution(int[][] board, int r, int c) {
        int answer = getAnswer(board, r, c);
        return answer;
    }
    private static int getAnswer(int[][] board, int r, int c) {
        if(finished(board)) return 0;
        int ret = 987654321;
        for (int num = 1; num <= 6; num++) {
            Point head = null, tail = null;
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    if(board[i][j] == num){
                        if(head == null) head = new Point(i, j);
                        else tail = new Point(i, j);
                    }
                }
            }
            // 해당 숫자는 이미 제거됨
            if(head == null) continue;
            // 앞에꺼 먼저 뒤집기 + 각 카드마다 Enter
            int headDist = getDist(r, c, head.x, head.y, board) +
                getDist(head.x, head.y, tail.x, tail.y, board) + 2;
            // 뒤에꺼 먼저 뒤집기 + 각 카드마다 Enter
            int tailDist = getDist(r, c, tail.x, tail.y, board) +
                getDist(tail.x, tail.y, head.x, head.y, board) + 2;
            // 뒤집은 카드 제거
            board[head.x][head.y] = board[tail.x][tail.y] = 0;
            int next = Math.min(headDist + getAnswer(board, tail.x, tail.y),
                                tailDist + getAnswer(board, head.x, head.y));
            ret = Math.min(ret, next);
            // 뒤집은 카드 원상복구
            board[head.x][head.y] = board[tail.x][tail.y] = num;
        }
        return ret;
    }
    private static boolean finished(int[][] board) {
        for (int[] row : board)
            for (int v : row)
                if(v != 0) return false;
        return true;
    }
    private static int getDist(int x, int y, int px, int py, int board[][]) {
        // 4가지 방향으로 ctrl 키를 눌러서 이동해보면서,
        // 가장 적은 비용으로 목적지에 도달하는 경우를 저장한다.
        PriorityQueue<Route> pq = new PriorityQueue<>((a, b) -> (a.cost - b.cost));
        pq.add(new Route(x, y, 0));
        int dist[][] = new int[4][4];
        for (int i = 0; i < 4; i++)
            Arrays.fill(dist[i], 987654321);
        dist[x][y] = 0;
        while (!pq.isEmpty()) {
            Route e = pq.poll();
            if(e.cost > dist[e.u][e.v]) continue;
            if(e.u == px && e.v == py)
                return e.cost;
            for (int d = 0; d < 4; d++) {
                int nx = e.u, ny = e.v, moveCnt = 0;
                while(isBorder(nx + dx[d], ny + dy[d])) {
                    nx += dx[d]; ny += dy[d];
                    moveCnt += 1;
                    // 다른 숫자 카드 발견
                    if(board[nx][ny] != 0) break;
                    // Ctrl 키를 누르지 않고 하나씩 이동하는 경우도 카운트 해준다.
                    if(dist[nx][ny] > e.cost + moveCnt){
                        dist[nx][ny] = e.cost + moveCnt;
                        pq.add(new Route(nx, ny, dist[nx][ny]));
                    }
                }
                // 카드 or 벽을 만나면 Ctrl 키를 눌러 한번에 이동 가능
                if(dist[nx][ny] > e.cost + 1){
                    dist[nx][ny] = e.cost + 1;
                    pq.add(new Route(nx, ny, dist[nx][ny]));
                }
            }
        }
        return 999999;
    }
    private static boolean isBorder(int x, int y) {
        return (x >= 0 && x < 4 && y >= 0 && y < 4);
    }
    public static void main(String[] args) {
        int board1[][] = {
            {1,0,0,3},
            {2,0,0,0},
            {0,0,0,2},
            {3,0,1,0}
        };
        int board2[][] = {
            {3,0,0,2},
            {0,0,1,0},
            {0,1,0,0},
            {2,0,0,3}
        };
        System.out.println(solution(board1, 1, 0));
        System.out.println(solution(board2, 0, 1));
    }
}