#include <stdio.h>
#include <math.h>
 
#define N 4
 
int search(int board[N][N], int min, int limit, int l_0, int m_0, char mv);
 
int main(int argc, char *argv[])
{
  int board[N][N];
  int md;
  int i, j, l, m, l_0, m_0, found;
  int res;
 
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) scanf("%d", &board[i][j]);
  }
 
  md = 0;
  for (i = 0; i < N * N; i++) {
    found = 0;
    for (l = 0; l < N; l++) {
      for (m = 0; m < N; m++) {
    if (board[l][m] == i) {
      if (i == 0) {
        l_0 = l;
        m_0 = m;
      } else md += (int)fabs((i-1)/N - l) + (int)fabs((i-1)%N - m);
      found = 1;
      break;
    }
      }
      if (found == 1) break;
    }
  }
 
  for (i = 0; ; i += 2) {
    if ((l_0 + m_0) % 2 == 0) {
      if (md % 2 == 0) res = search(board, md, md+i, l_0, m_0, 'c');
      else res = search(board, md, md+i+1, l_0, m_0, 'c');
    } else {
      if (md % 2 == 0) res = search(board, md, md+i+1, l_0, m_0, 'c');
      else res = search(board, md, md+i, l_0, m_0, 'c');
    }
 
    if (res != -1) break;
  }
 
  printf("%d\n", res);
 
  return 0;
}
 
int search(int board[N][N], int min, int limit, int l_0, int m_0, char mv)
{
  int md_c[4];
  int op[4], num[4];
  int res[4];
  int n;
  char dir[5] = "nswe";
 
  if (min == 0) return 0;
 
  for (n = 0; n < 4; n++) {
    md_c[n] = min;
    res[n] = -1;
  }
  op[0] = l_0-1;
  op[1] = l_0+1;
  op[2] = m_0-1;
  op[3] = m_0+1;
 
  if (op[0] >= 0) {
    if (mv != 's') {
      num[0] = board[op[0]][m_0];
      md_c[0] -= (int)fabs((num[0]-1)/N - op[0]);
      md_c[0] += (int)fabs((num[0]-1)/N - l_0);
    }
  }
  if (op[1] <= N-1) {
    if (mv != 'n') {
      num[1] = board[op[1]][m_0];
      md_c[1] -= (int)fabs((num[1]-1)/N - op[1]);
      md_c[1] += (int)fabs((num[1]-1)/N - l_0);
    }
  }
  if (op[2] >= 0) {
    if (mv != 'e') {
      num[2] = board[l_0][op[2]];
      md_c[2] -= (int)fabs((num[2]-1)%N - op[2]);
      md_c[2] += (int)fabs((num[2]-1)%N - m_0);
    }
  }
  if (op[3] <= N-1) {
    if (mv != 'w') {
      num[3] = board[l_0][op[3]];
      md_c[3] -= (int)fabs((num[3]-1)%N - op[3]);
      md_c[3] += (int)fabs((num[3]-1)%N - m_0);
    }
  }
 
  for (n = 0; n < 4; n++) {
    if (md_c[n] - min == -1) {
      if (n / 2 == 0) {    
    board[op[n]][m_0] = 0;
    board[l_0][m_0] = num[n];
    res[n] = search(board, md_c[n], limit-1, op[n], m_0, dir[n]);
    if (res[n] == -1) {
      board[op[n]][m_0] = num[n];
          board[l_0][m_0] = 0;
    } else res[n]++;
      } else {
    board[l_0][op[n]] = 0;
    board[l_0][m_0] = num[n];
    res[n] = search(board, md_c[n], limit-1, l_0, op[n], dir[n]);
    if (res[n] == -1) {
          board[l_0][op[n]] = num[n];
          board[l_0][m_0] = 0;
        } else res[n]++;
      }
    }
 
    if (res[n] != -1) break;
  }
 
  for (n = 0; n < 4; n++) {
    if (md_c[n] - min == 1) {
      if (md_c[n] <= limit - 1) {
    if (n / 2 == 0) {
      board[op[n]][m_0] = 0;
      board[l_0][m_0] = num[n];
      res[n] = search(board, md_c[n], limit-1, op[n], m_0, dir[n]);
      if (res[n] == -1) {
        board[op[n]][m_0] = num[n];
        board[l_0][m_0] = 0;
      } else res[n]++;
    } else {
      board[l_0][op[n]] = 0;
      board[l_0][m_0] = num[n];
      res[n] = search(board, md_c[n], limit-1, l_0, op[n], dir[n]);
      if (res[n] == -1) {
        board[l_0][op[n]] = num[n];
        board[l_0][m_0] = 0;
      } else res[n]++;
    }
      } else res[n] = -1;
    }
  }
 
  if (res[0] == -1 && res[1] == -1 && res[2] == -1 && res[3] == -1) return -1;
  else if (res[0] != -1) return res[0];
  else if (res[1] != -1) return res[1];
  else if (res[2] != -1) return res[2];
  else return res[3];
}



Measured memory_bytes: 2096