101 - The Blocks Problem

Problem.png

以题中的10块木块为例，即有10个位置，一开始从0到9依次放在10个位置上，然后机器人执行输入的指令，move a onto b 就是把a号和b号块上叠放着的的所有块归位(即0回到0位置，1回到1位置，依次类推)，然后把a放到b上(a紧贴着b所以是onto)，pile a onto b 就是把a和a上放着的所有块一起放在b上(紧贴着)，move a over b就是把a上放着的所有块归位，然后直接放在b那堆上(不用紧贴b)，pile a over b 意义类推。注意a和b在同一堆的话为无效指令，直接跳过不执行。
因此本题就是要模拟移动木块的过程，每个木块堆中木块的数目不确定，即每堆的高度不确定，所以可以用一个vector来保存一个木块堆，而木块堆的个数不超过N，所以可以用一个数组来保存所有堆，因此最后使用了vector的数组来组织数据。
接下来就是模拟各种操作，其实仔细分析后可以发现，四种命令全是由两种操作组成：

1. 将块a上的所有块归位
2. 把块a和a上的所有块都叠放到块b所在的那一堆

可以分别写成两个函数。
当然首先要根据指令找到块a和块b的位置，哪一堆哪一块。因为需要两个值来定位一个块，所以寻找块位置的函数需要使用引用作为参数来返回值。
然后移动块的操作可以用各种pop_back()和push_back()还有一个栈辅助完成，注意栈的top()函数的返回值是引用，直接把返回值作为push_back等其他函数的参数会出错，得用一个临时变量存储返回值(好像不仅是top会这样，所以push_back的参数都用临时变量来传就好了)。而pop_back()返回值为空，因此要先用下标获取vector的最后一个值然后再pop_back()。

但是，上面这种方法其实是麻烦了。。看了书才发现可以用下标索引把(例如b块)之上的块都push_back到另一个堆尾部，然后对原来的堆直接调用resize()调整大小，只保留下标0~b块，后面的块丢掉就行了，真是简单粗暴。。

要点：
以引用作为参数使函数可以返回多个值。
vector的用法，push_back，pop_back，resize，size等函数的灵活运用。
把每项具体的功能抽象为一个函数，使程序逻辑清晰。

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

const int maxn = 26;

int N;

vector<int> pile[maxn];

void find_pos(int num, int& p, int& h) {
    for (p = 0; p < N; p++) {
        for (h = 0; h < pile[p].size(); h++) {
            if (pile[p][h] == num) return;
        }
    }
}

void clear_above(int p, int h) {
    for (int i = pile[p].size() - 1; i > h; i--) {
        int num = pile[p][pile[p].size() - 1];
        pile[p].pop_back();
        pile[num].push_back(num);
    }
}

void pile_over(int pa, int ha, int pb, int hb) {
    stack<int> s;
    for (int i = pile[pa].size() - 1; i >= ha; i--) {
        int num = pile[pa][pile[pa].size() - 1];
        pile[pa].pop_back();
        s.push(num);
    }
    while (!s.empty()) {
        int top_num = s.top();
        pile[pb].push_back(top_num);
        s.pop();
    }
}

void print_pile() {
    for (int i = 0; i < N; i++) {
        if (pile[i].empty()) {
            cout << i << ':' << endl;
        }
        else {
            cout << i << ':';
            for (int j = 0; j < pile[i].size(); j++) {
                cout << ' ' << pile[i][j];
            }
            cout << endl;
        }
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        pile[i].push_back(i);
    }
    while (1) {
        string cmd1, cmd2;
        int a, b;
        cin >> cmd1;
        if (cmd1 == "quit") break;
        cin >> a >> cmd2 >> b;
        int pa, ha, pb, hb;
        find_pos(a, pa, ha);
        find_pos(b, pb, hb);
        if (pa == pb) continue;
        if (cmd1 == "move" && cmd2 == "onto") {
            clear_above(pa, ha);
            clear_above(pb, hb);
            pile_over(pa, ha, pb, hb);
        }
        else if (cmd1 == "move" && cmd2 == "over") {
            clear_above(pa, ha);
            pile_over(pa, ha, pb, hb);
        }
        else if (cmd1 == "pile" && cmd2 == "onto") {
            clear_above(pb, hb);
            pile_over(pa, ha, pb, hb);
        }
        else if (cmd1 == "pile" && cmd2 == "over") {
            pile_over(pa, ha, pb, hb);
        }
    }
    print_pile();
    return 0;
}

上面是我的代码，然而还是汝佳巨牛写的代码简洁优雅。。见书P110~111