Preparing NOJ

双轨车皮编序问题

1000ms 65536K

Description:

在一个列车调度站中,2 条轨道连接到2条侧轨处,形成2 个铁路转轨栈。其中左边轨道为车皮入口,编号为A;右边轨道为出口,编号为D2 个铁路转轨栈分别编号为CD,如下图所示。编号为ab,…,的n 个车皮依序停放在车皮入口处。调度室要安排各车皮进出栈次序,使得在出口处各车皮按照预先指定的顺序依次出站。车皮移动时只能按照从左到右的方向移动。

给定车皮数n,以及各车皮的出站顺序,编程计算最优调度方案,使得移动车皮的总次数最少。

Input:

第一行有1 个正整数n,表示车皮数。接下来的1 行中,是预先指定的车皮出站顺序。

Output:

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

Sample Input:

3
Abc

Sample Output:

5
c A B
b A B
a A D
b B D
c B D

Note:

undefined

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

Info

NOJ

Provider NOJ

Code NOJ1300

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet