破译密码

题目描述:

残雪取到了毛剑后，经过300多个回合的鏖战，终于打败了门卫。

于是胜利之后，他们便进入了藏宝洞，见到了神龙见首不见尾的zxb法师。法师见到他们很高兴，便语重心长地对他们说到：这里的宝藏是oi先人们几世几年累积下来的，也是我4000年来整日泡在网上下载来的。现在，终于派上用场了。但由于年初，天神dzd发布oi届有史以来最震撼的布告后，这里的宝藏便被上了诅咒，只有能解破宝盒上密码的人才能最终拿到这无尽的oi宝藏。而这需要勇气、信心、毅力。。。。。。

宝盒上是一个4*4的表格矩阵，0~F这16（十六进制）个数字分布在其中。这十六个数并不是固定的，而是可以移动的。移动规则如下：

1、横向：

第一行与第二行可以互换。

第二行和第三行可以互换

第三行和第四行可以互换

2.、纵向：

第一列与第二列可以互换。

第二列和第三列可以互换

第三列和第四列可以互换

矩阵的下面还有一个格子，需要填入把矩阵中的数字变成如下形式的最短变换次数，只有数字填对才能得到宝藏。

0   1   2   3

4   5   6   7

8   9   A   B

C   D   E   F

所有数据的最短步数不超过50。

输入格式:

4*4的矩阵，内容为1~F这16个数(每一行的相邻数字之间没有空格)

输出格式:

一个数，即最短步数

样例输入:

4567
0123
89AB
CDEF

样例输出:

1

提示:

所有数据保证有解

时间限制: 1000ms
空间限制: 128MB

---