UVa 101 The Blocks Problem 数据结构专题

UVa 101 The Blocks Problem 数据结构专题2014-10-06 csdn博客 shuangde800题目链接：

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=37

题目类型：数据结构，二叉树

题意：

有N个位置，编号为 0～N-1，初始下，各个位置上放置这和位置编号相同的砖块，即砖块1，砖块2……砖块N-1。然后有四种命令操作方式：

1.move a onto b :把砖a移动到砖b上面，如果a和b上面都有砖块，要先把它们放回原来位置。

2.move a over b: 把a移动到有b的“砖堆”上面，移动前需要把a上面的砖块都恢复到原位置，b的堆保持不变。

3.pile a onto b：把a之上的（包括a）搬到b之上，要先把b上面的砖放回到原来位置

4.pile a over b: 直接把a之上的（包括a）搬到b所在的“砖堆”上。

5.quit: 结束命令。

解体思路：初刚看到时，想用stack模拟，但是这样操作会比较多，可能会TLE。于是自己模拟写了类似栈的类，但是可以随机存储。 STL确实用起来比较方便，但是很不灵活。

#include<cstdio>#include<iostream>#include<string>using namespace std;int n, block_a, block_b, pos_a, pos_b;string command1,command2;class Pile{public:Pile（）{ index = 0; }void init_set（int a）{index=0;arr[index++] = a;}int top（）{return arr[index-1];}void add（int a）{arr[index++] = a;}bool is_empty（）{if（index==0）return true;return false;}int find（int a）{ for（int i=0; i<index; ++i）{ if（arr[i]==a） return i; } return -1;}void output（）{if（index！=0）{for（int i=0; i<index; ++i）{printf（" %d",arr[i]）;}}}int arr[100];int index;};Pile arr[100];// 找到砖块a所在的堆。 // 本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45539.htmint find_block（int a）{int result;for（int i=0; i<n; ++i）{result=arr[i].find（a）;if（result！=-1） return i;}}// 把砖块a之上的砖块全都返回初始位置。pos时砖堆位置void return_block（int pos, int a）{if（arr[pos].top（）==a） return;int index=arr[pos].find（a）;for（int i=index+1; i<arr[pos].index; ++i）{int temp=arr[pos].arr[i];arr[temp].init_set（temp）;}arr[pos].index = index+1;}void move_a_onto_b（int a,int b）{if（a==b） return ;pos_a = find_block（a）;pos_b = find_block（b）;if（pos_a==pos_b）return ;return_block（pos_a, a）;return_block（pos_b, b）;arr[pos_b].add（a）;--arr[pos_a].index;}void move_a_over_b（int a,int b）{if（a==b） return ;pos_a = find_block（a）;pos_b = find_block（b）;if（pos_a==pos_b）return ; return_block（pos_a, a）;arr[pos_b].add（a）;--arr[pos_a].index;}void pile_a_onto_b（int a,int b）{if（a==b） return ;pos_a = find_block（a）;pos_b = find_block（b）;if（pos_a==pos_b）return ; return_block（pos_b,b）;int index=arr[pos_a].find（a）;for（int i=index; i<arr[pos_a].index; ++i）{arr[pos_b].add（arr[pos_a].arr[i]）;}arr[pos_a].index = index;}void pile_a_over_b（int a,int b）{if（a==b） return ;pos_a = find_block（a）;pos_b = find_block（b）;if（pos_a==pos_b）return ;int index = arr[pos_a].find（a）;for（int i=index; i<arr[pos_a].index; ++i）{arr[pos_b].add（arr[pos_a].arr[i]）;}arr[pos_a].index = index;}void solve（）{if（command1=="move" && command2=="onto"）{move_a_onto_b（block_a,block_b）;}else if（command1=="move" && command2=="over"）{move_a_over_b（block_a,block_b）;}else if（command1=="pile" && command2=="onto"）{pile_a_onto_b（block_a,block_b）;}else if（command1=="pile" && command2=="over"）{pile_a_over_b（block_a,block_b）;}}void init（int n）{for（int i=0; i<n; ++i）{arr[i].init_set（i）;}}void output（）{for（int i=0; i<n; ++i）{printf（"%d:",i）;arr[i].output（）;printf（"
"）;}}int main（）{freopen（"input.txt","r",stdin）;scanf（"%d",&n）;init（n）;while（ cin >> command1 >> block_a >> command2 >> block_b）{if（command1=="quit"） break;solve（）;}output（）;return 0;}