一 问题描述

在早期的人工智能规划和机器人研究中使用了一个区块世界，在这个世界中，机器人手臂执行涉及区块操作的任务。问题是解析一系列命令，这些命令知道机器人手臂如何操作平板上的块。最初，有 n 个区块（编号从 0 到 n~1），如下图所示。

命令如下：

move a onto b：把 a 和 b 上方的块全部放回初始位置，然后把 a 放到 b 上方。

move a over b：把 a 上方的块全部放回初始位置，然后把 a 放到 b 所在块堆的最上方。

pile a onto b：把 b 上方的块全部放回初始位置，然后把 a 和 a 上方所有块整体放到 b 上方。

pile a over b：把 a 和 a 上方所有块整体放到 b 所在块堆的最上方。

quit：结束标志。

任何 a = b 或 a 和 b 在同一堆块中的命令都是非法命令。所有非法命令都应被忽略。

输入：输入的第行为整数 n，表示区块世界中的块数。后面是一系列块命令，每行一个命令。在遇到 quit 命令之前，程序应该出来所有命令。所有命令都将采用上面指定的格式，不会有语法错误的命令。

输出：输出应该包含区块世界的最终状态。每一个区块后面都有一个冒号。如果上面至少有一个块，则冒号后面必须跟一个空格，后面跟一个显示位置的块列表，每个块号与块号之间用空格隔开。

输入样例
10

move 9 onto 1

move 8 over 1

move 7 over 1

move 6 over 1

pile 8 over 6

pile 8 over 5

move 2 over 1

move 4 over 9

quit

输出样例

0：0

1：1 9 2 4

2：

3：3

4：

5：5 8 7 6

6：

7：

8：

9：

二 思路

初始时从左到右有 n 个块，编号从 0 到 n-1，要求实现一些操作。通过这些操作可以归纳总结出以下规律。

move：将 a 上方的块全部放回初始位置。

noto：将 b 上方的块全部放回初始位置。

公共操作：将 a 和 a 上方的所有块整体放到 b 所在块堆的最上方。

而实际上，前两种可以算一个操作：将 a 或 b 上方的块全部放回初始位置，简称归位。将 a 和 a 上方的所有块整体放到 b 所在块堆的最上方，简称移动。

只需要通过判断执行归位和移动操作就可以了。

三 算法设计

1 读取操作命令 s1，如果 s1="quit"，则结束；否则执行下面两步。

2 读入操作命令 a s2 b，如果 s1="move"，则 a 归位；如果 s2="onto"，则 b 归位。

3 执行移动操作，即将 a 和 a 上方所有的块整体放到 b 所在堆块的最上方。

四 归位操作

要想使 a 上方的所有块归位，则首先要找到 a 所在的堆块，并知道 a 在堆块中的位置（高度），然后才能将 a 上方的所有块归位。

例如，将 8 上方所有块归位。首先查找 8 所在的堆块为1，8所在堆块的高度为2，然后将 1 号块堆大于 2 的所有块放回原来的位置。

五 移动操作

要想让 a 和 a 上方所有块整体放到 b 所在块的最上方，则首先要找到 a 和 b 所在的块堆，如果 a、b 所在块堆一样，则什么都不做。否则，将 a 块堆中高度大于或等于 h（a的高度）的所有块移动到 b 所在块堆的上方。

例如，将 8 和 8 上方所有块整体放到 9 所在块堆的最上方。首先查找到 8 所在的块堆为 5 号，9 所在的块堆为 1 号，8 所在的块堆的高度为 1，然后将 5 号块堆高度大于或等于 1 的所有块放到 1 号块堆的上方。

六 图解

初始值：

1 move 9 onto 1

2 move 8 over 1

3 move 7 over 1

4 move 6 over 1

5 pile 8 over 6

什么都不做。

6 pile 8 over 5

7 move 2 over 1

8 move 4 over 9

9 quit：结束

10 从左到右、从下到上输出每个位置的块编号。

七 实现

package vector;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Vector;

class Pos {
    private Integer p;
    private Integer h;

    public Integer getP() {
        return p;
    }

    public void setP(Integer p) {
        this.p = p;
    }

    public Integer getH() {
        return h;
    }

    public void setH(Integer h) {
        this.h = h;
    }

    public Pos(Integer p, Integer h) {
        this.p = p;
        this.h = h;
    }
}

public class BlockTest {
    // 构造队列
    private static List<Vector<Integer>> blocks = new ArrayList<>();
    // 多少个块
    private static int n = 0;

    // 找位置
    static void loc(int x, Pos pos) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < blocks.get(i).size(); j++) {
                if (blocks.get(i).get(j) == x) {
                    pos.setP(i);
                    pos.setH(j);
                }
            }
        }
    }

    // 将p块堆高度大于 h 的所有块归位
    static void goBack(int p, int h) {
        for (int i = h + 1; i < blocks.get(p).size(); i++) {
            int k = blocks.get(p).get(i);
            blocks.get(k).addElement(k);
        }
        blocks.get(p).setSize(h + 1);
    }

    // 将 p 块堆高度大于或等于 h 的所有块都移动到 q 块堆的上方
    static void moveAll(int p, int h, int q) {
        for (int i = h; i < blocks.get(p).size(); i++) {
            int k = blocks.get(p).get(i);
            blocks.get(q).addElement(k);
        }
        blocks.get(p).setSize(h);
    }

    public static void main(String[] args) {
        // 初始化
        for (int i = 0; i <= 30; i++) {
            blocks.add(new Vector());
        }
        Scanner input = new Scanner(System.in);

        n = input.nextInt();
        for (int i = 0; i < n; i++) {
            blocks.get(i).addElement(i);
        }

        int a;
        int b;
        String s1;
        String s2;
        while (true) {
            s1 = input.next();
            if (s1.equals("quit")) {
                break;
            }
            a = input.nextInt();
            s2 = input.next();
            b = input.nextInt();
            Integer ap = 0;
            Integer ah = 0;
            Integer bp = 0;
            Integer bh = 0;
            Pos pos1 = new Pos(ap, ah);
            loc(a, pos1);
            Pos pos2 = new Pos(bp, bh);
            loc(b, pos2);
            if (pos1.getP() == pos2.getP()) {
                continue;
            }
            if (s1.equals("move")) {
                goBack(pos1.getP(), pos1.getH());
            }
            if (s2.equals("onto")) {
                goBack(pos2.getP(), pos2.getH());
            }
            moveAll(pos1.getP(), pos1.getH(), pos2.getP());
        }

        for (int i = 0; i < n; i++) {
            System.out.print(i + ":");
            for (int j = 0; j < blocks.get(i).size(); j++) {
                System.out.print(" " + blocks.get(i).get(j));
            }
            System.out.println();
        }
    }
}

八 测试

绿色为输入，白色为输出