码农场
Q101: The Blocks Problem
在早期人工智慧的领域中常常会用到机器人，在这个问题中有一支机器手臂接受指令来搬动积木，而你的任务就是输出最后积木的情形。
一开始在一平坦的桌面上有n块积木（编号从0到n-1）0号积木放在0号位置上，1号积木放在1号位置上，依此类推，如下图。
机器手臂有以下几种合法搬积木的方式（a和b是积木的编号）：
-
move a onto b
在将a搬到b上之前，先将a和b上的积木放回原来的位置（例如：1就放回1的最开始位罝） -
move a over b
在将a搬到b所在的那堆积木之上之前，先将a上的积木放回原来的位罝（b所在的那堆积木不动） -
pile a onto b
将a本身和其上的积木一起放到b上，在搬之前b上方的积木放回原位 -
pile a over b
将a本身和其上的积木一起搬到到b所在的那堆积木之上 -
quit
动作结束
前四个动作中若a=b，或者a, b在同一堆积木中，那么这样的动作算是不合法的。所有不合法的动作应该被忽略，也就是对各积木均无改变。
Input
输入含有多组测试资料，每组测试资料的第一列有一个正整数n（0 < n < 25），代表积木的数目（编号从0到n-1）。接下来为机器手臂的动作，每个动作一列。如果此动作为 quit ，代表此组测试资料输入结束。你可以假设所有的动作都符合上述的样式。请参考Sample Input。
Output
每组测试资料输出桌面上各位置积木的情形（每个位置一列，也就是共有n列），格式请参考Sample Output。
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 4 pile 0 over 1 pile 2 over 3 move 1 onto 3 quit
Sample Output
0: 0 1: 1 9 2 4 2: 3: 3 4: 5: 5 8 7 6 6: 7: 8: 9: 0: 0 1: 2: 2 3: 3 1
简体中文由Lucky貓的 UVA（ACM）園地转换。
没什么难的，纯粹if else，无非过程复杂。
需要注意：
①这题数据结构千万不要用deque，TLE。换list过了。我也不知道我怎么糊涂地用了双头队列。
//#pragma warning(disable : 4996)
#include <iostream>
#include <string>
#include <algorithm>
#include <list>
using namespace std;
#define MAX 25
int n = 0;
list<int> block[MAX];
typedef list<int>::iterator dit;
void print_blocks()
{
for (int i = 0; i < n; ++i)
{
cout << i << ':';
for (dit it = block[i].begin(); it != block[i].end(); ++it)
{
cout << ' ' << *it;
}
cout << endl;
}
}
list<int>::iterator search(int& index, const int& x)
{
for (index = 0; index < n; ++index)
{
list<int>::iterator it = find(block[index].begin(), block[index].end(), x);
if (it != block[index].end())
{
return it;
}
}
}
void restore(const int& index, dit itx)
{
++itx;
while (itx != block[index].end())
{
block[*itx].push_back(*itx);
itx = block[index].erase(itx);
}
}
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> n;
for (int i = 0; i < n; ++i)
{
block[i].clear();
block[i].push_back(i);
}
string cmd;
while (cin >> cmd)
{
if (cmd == "quit")
{
print_blocks();
break;
}
else
{
string param;
int a, b;
cin >> a >> param >> b;
if (a == b)
{
continue;
}
int na;
dit pa = search(na, a);
int nb;
dit pb = search(nb, b);
if (na == nb)
{
continue;
}
if (cmd == "move")
{
if (param == "onto")
{
restore(na, pa);
restore(nb, pb);
block[nb].push_back(*pa);
block[na].erase(pa);
}
else if (param == "over")
{
restore(na, pa);
block[nb].push_back(*pa);
block[na].erase(pa);
}
}
else if (cmd == "pile")
{
if (param == "onto")
{
restore(nb, pb);
while (pa != block[na].end())
{
block[nb].push_back(*pa);
pa = block[na].erase(pa);
}
}
else if (param == "over")
{
while (pa != block[na].end())
{
block[nb].push_back(*pa);
pa = block[na].erase(pa);
}
}
}
}
}
/*system("out.txt");*/
return 0;
}
///////////////////////////End Sub//////////////////////////////////
