Preparing NOJ

多轨车皮编序问题

1000ms 65536K

Description:

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

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

Input:

第一行有2 个正整数nk,表示车皮数为n和侧轨数为k。接下来的k+1 行中,表示编号为012,…,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导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1301

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet