华师一附中OI组

标题: 双栈列车调度 [打印本页]

作者: diggersun 时间: 2016-8-11 00:54
标题: 双栈列车调度
本帖最后由 diggersun 于 2016-8-11 00:56 编辑

2020年，很多工作已经由机器人来担当了，比如X火车站的列车调度员就是一个机器人。X车站很小，其结构如下图所示：
其中，A是车站的入口轨道，D是出口，B和C是两个长度足够的中转轨道(最底端没有出口)。所有的轨道都是单线，即任一时刻，至多只有一辆列车通过，所以，A端列车只能顺次进站，中转轨道B和C中，也只有最顶端的列车(如果有的话)可以移动。
调度员只可以执行下述6种调度操作(当然，他一次只能移动一辆可以移动的列车)：
让A端的进站列车进入B，记作A->B；
让A端的进站列车进入C，记作A->C；
让A端的进站列车直接移动到D出站，记作A->D；
让中转轨道B中的顶端列车移动到C的顶端，记作B->C；
让中转轨道B中的顶端列车移动到D出站，记作B->D;
让中转轨道C中的顶端列车移动到D出站，记作C->D。
作为列车调度员，digger的工作是这样的：每天早晨，有N辆列车从A端进站(不妨按进站顺序编号为1..N)，然后，他将要按照指令，通过调度操作，使列车按照某个给定的顺序出站。
然而，最近digger向HSY提出了申诉，因为他怀疑有些命令是否真的能够实现。所以，HSY委派你编写一个程序，根据给定的出站序列，判断是否存在可行的调度方案，更进一步的，如果这样的调度方案存在，请找出其中操作步数最少的一种（如有多种这样的方案，只需找到其中的一种即可）。

欢迎光临华师一附中OI组 (http://hsyit.cn/)