#P3221. 钻石游戏

    ID: 2231 远端评测题 2000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>第六届北京大学程序设计大赛暨ACM/ICPC选拔赛, wenxichang

钻石游戏

Description

一个钻石游戏是在图1所示的一个分割成数个面的六边形上进行的。在这个题目里,分隔出来的面按照图中所示方式进行标号。如果两个面公用一条边,那么成它们为相邻面。那么,偶数编号的面就有三个相邻面,奇数编号的面只有两个相邻面。在游戏进行中的任何时刻,七个面中的六个里会有一个唯一的1到6之间的数字,剩下的一个面则是空的。游戏中的一步就是将一个数字从一个面移动到一个空相邻面。

从任意开始状态出发,通过一系列移动可以让游戏的状态变成如图23所示之一。你的任务就是计算从开始状态出发到达图2中的状态最少需要多少步。

Input

输入包含多组测试数据。第一行包含一个整数N(0 ≤ N ≤ 5,040),测试数据的数目。接下来N行每行包含{0, 1, 2, 3, 4, 5, 6}的一个排列,描述游戏的一个开始状态。排列中的第i个数字表示标号为i − 1的面上的数字。零表示一个面是空的。

Output

对每组测试数据,输出从开始状态到达图2所示状态的最少步数。如果这是不可能的,输出“-1”。

3
1324506
2410653
0123456
10
-1
0

Source

第六届北京大学程序设计大赛暨ACM/ICPC选拔赛, wenxichang

Translator

Yingchong SITU 'frkstyc'