多轨车皮编序问题

Description:

在一个列车调度站中，k条轨道连接到k条侧轨处，形成k个铁路转轨栈，从左到右依次编号为1，2，…，k。其中左边轨道为车皮入口，编号为0；右边轨道为出口，编号为k+1。当k=2 时，如下图所示。编号为1，2，…，n的n个车皮散乱地停放在编号为0，1，2，…，k的栈轨处。调度室要安排各车皮进出栈次序，使得在出口处各车皮按照其编号次序1，2，…，n依次出站。车皮移动时只能按照从左到右的方向移动。

给定车皮数n和侧轨数k，以及各车皮的位置，编程计算最优调度方案，使得移动车皮的总次数最少。

Input:

第一行有2 个正整数n和k，表示车皮数为n和侧轨数为k。接下来的k+1 行中，表示编号为0，1，2，…，k 的栈轨处按照从下到上的顺序停放的车皮序列。每行的第一个数表示该栈轨处的车皮数，紧接着是车皮序列。

Output:

文件的第一行是最少移动次数m。接下来的m行是对应于最优方案的m次移动。每次移动用形如‘c x y’的3个整数来表示，其中c 表示车皮编号，x 表示起始栈轨号，y 表示目标栈轨号。如果无法调度则输出“NoSolution!”。

Sample Input:

6 2
4 4 1 5 3
2 6 2
0

Sample Output:

9
3 0 1
5 0 2
1 0 3
3 1 2
2 1 3
3 2 3
4 0 3
5 2 3
6 1 3

Note:

undefined

本题由旧版NOJ导入，来源：算法设计与实验题解