空格游戏

Grade 0 Open Time Wednesday, 16 January 2013, 2:05 pm
Discount 0.8 Time Discount Wednesday, 16 January 2013, 2:05 pm
Allow late Yes Close Time Wednesday, 16 January 2013, 2:05 pm
Input file gap.in Output file gap.out

问题描述
我们来玩一个叫空格的牌类游戏。你有28张用两位数标记的牌,第一位(从1到4)表示不同的花色,第二位(从1到7)表示牌的值。
首先,你先洗牌,然后将它们排成四行,每行七张,在每行的最左边留一张牌的位置。下面给出一个可能的最初排布。
 
 
42
21
13
22
32
26
23
 
16
43
47
14
24
34
36
 
46
17
27
31
11
37
12
 
35
41
44
25
15
33
45
 
下一步,你移动所有值为1的牌,将它们放在左边的空格里:11放在最上面,12放在下一格,如此放下去。
现在你有28张牌和4个空格,排成4行8列。如上述举例,你从下面情况开始移动。
 
11
42
 
13
22
32
26
23
21
16
43
47
14
24
34
36
31
46
17
27
 
 
37
12
41
35
 
44
25
15
33
45
 
每一步移动,你选择四个空格之一,将该空格左边的牌的后继牌放进去。后继牌是指同一花色的下一张牌。例如42的后继牌时42,27没有后继牌。
 
在上面的情况中,你可以将43移动到43的右边的空格中,或者将36移动到35的右边。例如你移动43,16的右边后产生一个新的空格。你不能将派移动到价值为7的牌的右边,也不能移动到空格的右边。
 
游戏的目标是,选择最佳移动,使得每种花色各自成上升序列,如下表。
 
11
12
13
14
15
16
17
 
21
22
23
24
25
26
27
 
31
32
33
34
35
36
37
 
41
42
43
44
45
46
47
 
 
你的任务是计算到达目标状态所需的最少移动。
 
输入格式
 
4行7列,表示初始状态。
 
输出格式
 
一个整数,到达目标状态所需的最少移动。最初移动4张值为1的牌的移动不算在内。如果没法到达,输出-1。
 
输入样例
26 31 13 44 21 24 42
17 45 23 25 41 36 11
46 34 14 12 37 32 47
16 43 27 35 22 33 15
 
输出样例
33