UVA - 101 The Blocks Problem

/* 收获： 1. 虽然不能返回两个值，但是可以用传引用作为参数，改变引用，来实现相同的效果 2. 不定长数组用 vecotr 保存比较合适 3. vector中的resize函数很好用，可以重新设定vector的长度，多余的元素全部删掉 有关resize()函数的更多介绍： http://blog.csdn.net/jocodeoe/article/details/9230879 4. 如果完全独立地处理各指令，代码就会变得冗长而且易错。更好的方法是，提取出指令的共同点，编写函数以减少重复代码 5.关于vector的几个函数： clear()清空，resize()改变大小，push_back()和pop_back()在尾部增加和删除元素，用empty()测试是否为空 且vector可直接赋值，或是作为函数的返回值 */

#include <cstdio> #include <string> #include <vector> #include <iostream> using namespace std; const int maxn = 30; int n; vector<int> pile[maxn]; //每个pile[i]都是一个vector //找木块a所在的pile和height, 以引用的形式返回调用者 void find_block(int a, int& p, int& h) { for (p = 0; p < n; p++) for (h = 0; h < pile[p].size(); h++) { if (pile[p][h] == a) return; } } //把第p堆高度为h的木块上方的所有木块移回原位 void clear_above(int p, int h) { for (int i = h + 1; i < pile[p].size(); i++) { int b = pile[p][i]; pile[b].push_back(b); //把木块b放回原位 } pile[p].resize(h + 1); //pile只应保留下标 0~h 的元素 } //把第p堆高度为h及其上方的木块整体移动到p2堆的顶部 void pile_onto(int p, int h, int p2) { for (int i = h; i < pile[p].size(); i++) pile[p2].push_back(pile[p][i]); pile[p].resize(h); } void print() { for (int i = 0; i < n; i++) { printf("%d:", i); for (int j = 0; j < pile[i].size(); j++) printf(" %d", pile[i][j]); printf("\n"); } } int main() { int a, b; string s1, s2; cin >> n; for (int i = 0; i < n; i++) pile[i].push_back(i); while (cin >> s1) { if (s1 == "quit") break; cin >> a >> s2 >> b; int pa, pb, ha, hb; find_block(a, pa, ha); find_block(b, pb, hb); if (pa == pb) continue; //a和b在同一堆，非法指令 if (s2 == "onto") clear_above(pb, hb); if (s1 == "move") clear_above(pa, ha); pile_onto(pa, ha, pb); } print(); return 0; }