题目描述

十五数码是一块 $4\times 4$ 的活动拼板，上面有 $1\sim 15$ 共 $15$ 个数字块和一个空格（用 $0$ 表示）。每次操作可以把空格上、下、左、右四个方向相邻的一个数字块滑进空格，也就是空格与那块数字互换位置。

目标状态是：

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 0

现在给出一个初始状态，请回答：至少要操作多少次才能变成目标状态？如果无论怎样都做不到，输出 $-1$。

输入格式

共 $4$ 行，每行 $4$ 个整数，表示初始状态（$0$ 表示空格，$1\sim 15$ 各出现一次）。

输出格式

一行一个整数，表示最少操作次数；不可达时输出 $-1$。

输入输出样例 #1

输入 #1

1 2 3 4
5 6 7 8
9 10 11 12
13 14 0 15

输出 #1

1