【UVA 101】The Blocks Problem 题解（模拟+向量）

计算机科学的许多领域使用简单、抽象的领域进行分析和实证研究。

例如，早期的人工智能规划和机器人研究（STRIPS）使用了一个区块世界，其中机器人 arm执行涉及块操作的任务。 在这个问题中，您将在某些规则和约束下对一个简单的块世界进行建模。相当地 与确定如何达到指定状态相比，您将“编程”机器人手臂以响应 有限的命令集。 问题是解析一系列命令，指导机器人手臂如何操作块 躺在一张平桌子上。最初，表上有n个块（编号从0到n−1），带有块 bi与区块bi+1相邻，所有0≤i<n−1，如下图所示：

【UVA 101】The Blocks Problem 题解（模拟+向量）初始块世界 操纵块的机械臂的有效命令如下： •move a onto b 其中a和b是块号，在返回以下任何块后，将块a放到块b上 堆叠在块a和b的顶部至其初始位置。 •move a over b 其中a和b是块号，将块a放在包含块b的堆栈的顶部，之后 将堆叠在块a顶部的任何块返回到其初始位置。 •pile a onto b 其中a和b是块号，移动由块a和任何块组成的块堆 将堆叠在a块上方的所有块移动到b块上 打桩前的初始位置。堆叠在a块上方的块保持其顺序 当移动时。 •pile a over b 其中a和b是块号，将由块a和任何块组成的一堆块放入 堆叠在区块a上方的区块，放置在包含区块b的堆叠顶部 上面的块a在移动时保持其原始顺序。 •quit 终止块世界中的操作。 任何a=b或a和b位于同一块堆栈中的命令都是非法的 命令应忽略所有非法命令，并且不应影响 阻碍。

输入 输入以一行上的整数n开始，该整数n本身表示块中的块数 世界您可以假设0<n<25。 块的数量后面跟着一系列块命令，每行一个命令。你的 程序应处理所有命令，直到遇到退出命令。 您可以假设所有命令都是上面指定的格式。语法上不会有 错误的命令。 输出 输出应包含块世界的最终状态。每个原始块位置编号 i（0≤i＜n，其中n是块的数量）应紧跟冒号出现。如果有 至少是一个块，冒号后面必须跟一个空格，后面是出现的块列表 每个块号与其他块号隔开一个空格。不要 在一行中放置任何尾随空格。 每个块位置应有一行输出（即n行输出，其中n是 输入的第一行上的整数）。

Sample Input 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 Sample Output 0: 0 1: 1 9 2 4 2: 3: 3 4: 5: 5 8 7 6 6: 7: 8: 9:

思路

用一个vector数组储存方块摆放位置。对方块操作前应该定位它在vector数组中的位置。执行move前要将a块和它上面的块归位，执行onto前要将b块和它上面的块归位。注意应忽略所有a=b或a和b位于同一块堆中的非法命令。

AC代码

#include <iostream>
#include <vector>
#define AUTHOR "HEX9CF"
using namespace std;

int n;
vector<int> v[30];

void print()
{
    for (int i = 0; i < n; i++)
    {
        cout << i << ":";
        for (int j = 0; j < v[i].size(); j++)
        {
            cout << " " << v[i][j];
        }
        cout << endl;
    }
}

void find(int t, int *x, int *y)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < v[i].size(); j++)
        {
            if (t == v[i][j])
            {
                *x = i;
                *y = j;
                return;
            }
        }
    }
}

void reset(int x, int y)
{
    for (int i = y + 1; i < v[x].size(); i++)
    {
        int t = v[x][i];
        v[t].push_back(t);
    }
    v[x].resize(y + 1);
}

void move(int xa, int ya, int xb)
{
    for (int i = ya; i < v[xa].size(); i++)
    {
        int t = v[xa][i];
        v[xb].push_back(t);
    }
    v[xa].resize(ya);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        v[i].push_back(i);
    }
    string cmd1, cmd2;
    int a, b;
    int xa, ya, xb, yb;
    while (cin >> cmd1)
    {
        if ("quit" == cmd1)
        {
            break;
        }
        cin >> a >> cmd2 >> b;
        find(a, &xa, &ya);
        find(b, &xb, &yb);
        if (xa == xb)
        {
            continue;
        }
        if ("move" == cmd1)
        {
            reset(xa, ya);
        }
        if ("onto" == cmd2)
        {
            reset(xb, yb);
        }
        move(xa, ya, xb);
    }
    print();
    return 0;
}