UVa 101

The Blocks Problem

from Volume 2. Data Structures :: Lists

Description

平台上摆放着个 n 个积木（编号由 0 到 n – 1），初始位置为 0 到 n - 1。

你要模拟一个机械手臂的操作，机械手臂有四种指令：

• move a onto b：将 a 和 b 上的积木都放回初始位置，然后把 a 放在 b 上（a、b 紧贴着）。
• move a over b：将 a 上的积木放回初始位置，然后把 a 放在 b 堆上（a、b 隔开的）。
• pile a onto b： 将 b 上的积木放回初始位置， 然后把 a 堆放到 b 上（a、b 紧贴着）。
• pile a over b：把 a 堆 放在 b 堆上（a、b 隔开的）。
• quit：结束操作。

输入木快的数量，和一系列的指令，输出最终结果。注意当 a 和 b 在同一堆的时候，指令无效。

Solution

用顺序表，即建立两个数组，分别用来存储：

• 以某个积木为底的积木堆。
• 某块积木的位置。

模拟的时候注意维护两个数组即可。除了可以用顺序表，还可以用双向链表来做。

如果用双向链表，则需要维护：

• 每个节点的状态。
• 表示初始位置的节点的状态。
• 积木的位置。

本来对于这种大量的成段数据移动，用双向链表会较快，但是因为有无效指令，导致每次移动都要遍历去维护积木的位置，使得双向链表和顺序表的做法效率差不多。为了练习双向链表的使用，我用的是双向链表，并且是动态开辟空间的做法。如果单纯为了 AC，推荐用顺序表来做。