bzoj#P1840. Zju1742 Gap
Zju1742 Gap
题目背景
一起来玩一个叫 Gap 的游戏吧!
题目描述
你有 张双标号的牌,第一个标号代表牌的花色(从 到 ),第二个标号代表牌的大小(从 到 )。
一开始,你打乱这些牌并把他们重新摆成 行 列的方阵,再在每一行最左侧加入一个空位,如下图:
接着,你拿走所有大小为 的牌,并把他们按花色顺序放在最左侧的空位上( 在第一行,$21¥ 在第二行,以此类推)。现在这 行 列中,你有 个牌和 个空,如下图。
你可以做任意次移动:选择一个空位,把它左边的牌的后继移动到这个空位上。如果这个空位左边也是空位,或者左边的牌没有后继,那么无法移动。
后继的定义是同花色的牌中,大小比当前牌要大的牌中的最小的牌。如: 的后继是 , 没有后继。
在上面的例子中,你可以把 移动到 右边的空位中,或者把 移动到 右边的空位中。
这个游戏的目标是通过若干次操作,把每个花色的牌都放在同一行,如下图:
你需要通过最少的步数达成这个目标,输出最小的步数。
输入格式
行 列,表示初始状态。
输出格式
一个数表示答案,如果无解则输出 。
注意,输出的步数不包含一开始把一号牌放在最左边的步数。
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