bzoj#P1840. Zju1742 Gap

Zju1742 Gap

题目背景

一起来玩一个叫 Gap 的游戏吧!

题目描述

你有 2828 张双标号的牌,第一个标号代表牌的花色(从 1144),第二个标号代表牌的大小(从 1177)。

一开始,你打乱这些牌并把他们重新摆成 4477 列的方阵,再在每一行最左侧加入一个空位,如下图:

接着,你拿走所有大小为 11 的牌,并把他们按花色顺序放在最左侧的空位上(1111 在第一行,$21¥ 在第二行,以此类推)。现在这 4488 列中,你有 2828 个牌和 44 个空,如下图。

你可以做任意次移动:选择一个空位,把它左边的牌的后继移动到这个空位上。如果这个空位左边也是空位,或者左边的牌没有后继,那么无法移动。

后继的定义是同花色的牌中,大小比当前牌要大的牌中的最小的牌。如: 4242 的后继是 43432727 没有后继。

在上面的例子中,你可以把 4343 移动到 4242 右边的空位中,或者把 3636 移动到 3535 右边的空位中。

这个游戏的目标是通过若干次操作,把每个花色的牌都放在同一行,如下图:

你需要通过最少的步数达成这个目标,输出最小的步数。

输入格式

4477 列,表示初始状态。

输出格式

一个数表示答案,如果无解则输出 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