using System;
using System.Collections.Generic;
using System.Linq;
//Q091 15パズル https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_C&lang=jp
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("1 2 3 4");
WillReturn.Add("6 7 8 0");
WillReturn.Add("5 10 11 12");
WillReturn.Add("9 13 14 15");
//8
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
const int UB = 4 - 1;
static int[,] QuestionArr;
static int DepthLimit;
static int FirstDepthLimit;
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
QuestionArr = new int[UB + 1, UB + 1];
for (int Y = 0; Y <= UB; Y++) {
SplitAct(InputList[Y]);
for (int X = 0; X <= UB; X++) {
QuestionArr[X, Y] = wkArr[X];
}
}
bool HasEvenKai = true; //解の手数が偶数か？
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (QuestionArr[X, Y] == 0) {
HasEvenKai = ((X + Y) % 2 == 0);
}
}
}
FirstDepthLimit = (HasEvenKai ? 2 : 1);
for (DepthLimit = FirstDepthLimit; DepthLimit < int.MaxValue; DepthLimit += 2) {
bool FoundAnswer = false;
int MinTesuu = ExecDFS(out FoundAnswer);
if (FoundAnswer) {
Console.WriteLine(MinTesuu);
break;
}
}
}
struct JyoutaiDef
{
internal int Level;
internal int[,] BanArr;
internal char PreMove;
internal int[] NeedTesuuArr;
}
//反復深化深さ優先探索を行う
static int ExecDFS(out bool pFoundAnswer)
{
pFoundAnswer = false;
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Level = 0;
WillPush.BanArr = QuestionArr;
WillPush.PreMove = '\0';
WillPush.NeedTesuuArr = new int[15];
for (int I = 1; I <= 15; I++) {
WillPush.NeedTesuuArr[I - 1] = NeedMinTesuuForNum(QuestionArr, I);
}
Stk.Push(WillPush);
//盤面に対する最少手数のDict
var MinTesuuDict = new Dictionary<ulong, int>();
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
if (IsCorrectPlace(Popped.BanArr, 15)) {
pFoundAnswer = true;
return Popped.Level;
}
int X = 0, Y = 0;
while (Popped.BanArr[X, Y] != 0) {
if (++X > UB) {
Y++; X = 0;
}
}
WillPush.Level = Popped.Level + 1;
Action<int, int, char> PushSyori = (pFromX, pFromY, pPreMove) =>
{
int MoveNum = Popped.BanArr[pFromX, pFromY];
WillPush.BanArr = (int[,])Popped.BanArr.Clone();
WillPush.BanArr[X, Y] = MoveNum;
WillPush.BanArr[pFromX, pFromY] = 0;
WillPush.NeedTesuuArr = (int[])Popped.NeedTesuuArr.Clone();
WillPush.NeedTesuuArr[MoveNum - 1] = NeedMinTesuuForNum(WillPush.BanArr, MoveNum);
//下限値枝切り
int NeedTesuuSum = WillPush.NeedTesuuArr.Sum();
if (WillPush.Level + NeedTesuuSum > DepthLimit) return;
ulong BanULong = BanToULong(WillPush.BanArr);
//当該盤面に、少ない手数か等しい手数で、到達済なら枝切り
int MinTesuu;
if (MinTesuuDict.TryGetValue(BanULong, out MinTesuu)) {
if (MinTesuu <= WillPush.Level) return;
}
MinTesuuDict[BanULong] = WillPush.Level;
WillPush.PreMove = pPreMove;
Stk.Push(WillPush);
};
//左の数字を、右に移動
if (X > 0 && Popped.PreMove != '←') PushSyori(X - 1, Y, '→');
//右の数字を、左に移動
if (X < UB && Popped.PreMove != '→') PushSyori(X + 1, Y, '←');
//上の数字を、下に移動
if (Y > 0 && Popped.PreMove != '↑') PushSyori(X, Y - 1, '↓');
//下の数字を、上に移動
if (Y < UB && Popped.PreMove != '↓') PushSyori(X, Y + 1, '↑');
}
return -1;
}
//盤面を符号なしLong型で表現
static ulong BanToULong(int[,] pBan)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (pBan[X, Y] == 10) sb.Append('A');
else if (pBan[X, Y] == 11) sb.Append('B');
else if (pBan[X, Y] == 12) sb.Append('C');
else if (pBan[X, Y] == 13) sb.Append('D');
else if (pBan[X, Y] == 14) sb.Append('E');
else if (pBan[X, Y] == 15) sb.Append('F');
else sb.Append(pBan[X, Y]);
}
}
return Convert.ToUInt64(sb.ToString(), 16);
}
//1から指定した値までの位置が正しい位置かを返す
static bool IsCorrectPlace(int[,] pBanArr, int pToNum)
{
int MustNumber = 0;
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
++MustNumber;
if (pBanArr[X, Y] != MustNumber) return false;
if (MustNumber == pToNum) return true;
}
}
return true;
}
//指定した数字が正しい位置に到達するのに必要な、最少手数を求める
static int NeedMinTesuuForNum(int[,] pBanArr, int pTargetNum)
{
int X1 = 0, Y1 = 0;
if (pTargetNum == 1) { X1 = 0; Y1 = 0; }
if (pTargetNum == 2) { X1 = 1; Y1 = 0; }
if (pTargetNum == 3) { X1 = 2; Y1 = 0; }
if (pTargetNum == 4) { X1 = 3; Y1 = 0; }
if (pTargetNum == 5) { X1 = 0; Y1 = 1; }
if (pTargetNum == 6) { X1 = 1; Y1 = 1; }
if (pTargetNum == 7) { X1 = 2; Y1 = 1; }
if (pTargetNum == 8) { X1 = 3; Y1 = 1; }
if (pTargetNum == 9) { X1 = 0; Y1 = 2; }
if (pTargetNum == 10) { X1 = 1; Y1 = 2; }
if (pTargetNum == 11) { X1 = 2; Y1 = 2; }
if (pTargetNum == 12) { X1 = 3; Y1 = 2; }
if (pTargetNum == 13) { X1 = 0; Y1 = 3; }
if (pTargetNum == 14) { X1 = 1; Y1 = 3; }
if (pTargetNum == 15) { X1 = 2; Y1 = 3; }
int X2, Y2;
SearchNumXY(pBanArr, pTargetNum, out X2, out Y2);
return Math.Abs(X1 - X2) + Math.Abs(Y1 - Y2);
}
//指定した数字の存在する座標を返す
static void SearchNumXY(int[,] pBanArr, int pTargetNum, out int pX, out int pY)
{
pX = pY = -1;
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (pBanArr[X, Y] == pTargetNum) {
pX = X;
pY = Y;
return;
}
}
}
}
// 2次元配列のデバッグ出力
static void PrintBan(int[,] pBanArr)
{
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
Console.Write(pBanArr[X, Y]);
}
Console.WriteLine();
}
}
}