暂无测试数据。

Description

　　烦恼的设计师（来自SGOI）
　　春天到了，百花齐放，西湖公园里新设置了许多花坛，设计师想用不同的花摆出不同的图案以吸引游人，于是设计了各种图案并且在花圃中选好了要摆放的花。不幸的是负责搬运和摆放的工人因为临时有事，只将花放到花架上就匆匆离开了，并没有按照设计师原来的设计方案摆放，结果花坛杂乱不堪,设计师只好自己来调整花的位置。由于设计师通常从事脑力劳动，较少从事搬运和摆放花盆的体力工作，所以请你帮忙找出一种移动方法使工作量最小。
　　不同种类的花有不同的类型编号，虽然地球上花的种类很多，但因为公园里的花不超过1,000,000种，所以花的类型编号不超过1,000,000。另一方面，出于美学考虑，一个花坛里摆放的不同种类的花不超过3种，且不同种类的花的数量不可太接近，对于任意两种花，数量多的花的盆数至少是数量少的花的2倍。
　　花坛是正六边形的，共摆放有19盆花，每盆花都放在一个转盘上，转动一盆花下面的转盘，会使周围的6盆花顺时针或逆时针移动一个位置（但不可把花转到花坛外），称为一次操作。你的任务：用最少的操作使花坛由初始状态转化为符合设计图纸的目标状态。例如：

Input

　　输入文件共11行，1至5行描述花坛的初始状态，7至11行表示花盆应摆放的位置。中间以空行分隔，5行数字分别表示花坛的5个行，其中第1、5两行有3个整数，第2、4两行有4个整数，第3行有5个整数，表示每一行的花的类型，不同的数代表不同种类的花。

Output

　　输出文件，一行，包含一个整数，即最少的操作数，数据保证20步之内有解。

Sample Input

1 1 1
1 2 1 1
1 1 1 1 1
1 1 1 1
1 1 1

1 1 1
1 1 1 1
1 1 2 1 1
1 1 1 1
1 1 1

Sample Output

1

Limitation

1s, 65536KiB for each test case.

Hint

题意描述:
　　给定两个正6边形的花坛，要求求出从第一个变化到第二个的最小操作次数以及操作方式。一次操作是：选定不在边上的一盆花，将这盆花周围的6盆花按照顺时针或者逆时针的顺序依次移动一个单位。限定一个花坛里摆放的不同种类的花不超过3种，对于任意两种花，数量多的花的盆数至少是数量少的花的2倍 。（这是 SGOI-8 的一道题）

解题分析：
　　首先确定本题可以用广度优先搜索处理，然后来看问题的规模。正6边形共有19个格子可以用来放花，而且根据最后一句限定条件，至多只能存在 C(2,19) * C(5,17) = 1058148 种状态，用搜索完全可行。然而操作的时候，可以预料产生的重复节点是相当多的，需要迅速判重才能在限定时间内出解，因此想到了哈希表。那么这个哈希函数如何设计呢？注意到19个格子组成6边形是有顺序的，而且每一个格子只有3种可能情况，那么用3进制19位数最大 3^20-1=3486784400，注意，这个数值大于2^31，但小于2^32。于是我们将每一个状态与一个整数对应起来，使用除余法就可以了。

Source

GZOJ 1542