空格游戏
0 | 1 |
通过 | 提交 |
题目描述
我们来玩一个叫空格的牌类游戏。你有28张用两位数标记的牌。第一位(从l到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的牌,将它们放在左边的空格里:“1l”放在最上面,“21”
放在下一格,如此放下去。
现在,你有28张牌和4个空格,排成四行八列。如上所举例,你将从下面的情况开始
多动。
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”的后继牌是“43",“27"没有后继牌。
在上面的情况中,你可以将“43”移动到“42”右边的空格中,或者将“36”移动到“35"
右边。如果你移动“43”,“1 6”的右边会产生一个新的空格。你不能将牌移动到价值为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 |
你的任务是到达目标状态所需最少移动。
输入格式
四行,表示最初的四行牌。每行由七个两位数,对应每张牌。
输出格式
输出到达目标状态所需最少移动。注意,最初四张价值为1的牌的移动不算在内。如
果没法到达最终状态,输出-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
样例输出 #1
33