首页 > 代码库 > USTC OJ — 1004 Block world （数据结构stack，简单题）
USTC OJ — 1004 Block world （数据结构stack，简单题）
1. 题目描述
本题描述了一个“机器人”的世界，初始状态如下所示：
现实世界中，机器人没有自主思想，只能接受指令去完成工作。类似地，题目中定义了下面的几种指令：
问题：给定一系列操作指令，计算出“机器人”在完成这些指令之后，“机器人”世界（即Block world）的状态。注意：指令操作结束是使用quit指令来完成。
2. 算法设计
问题很简单，显然需要用stack数据结构表示。
然后只需要把上面的指令描述清楚，模拟各个指令的操作设计出5个API来完成这5个指令即可。
简单地把上面五种机器人指令描述一下：
move a onto b:
先找到block a和block b所在的block stack，然后把压在a和b上面的所有block还原到初始stack（的栈顶位置）。最后把a弹出，压在b（所在的stack栈顶）上面。
move a over b:
先找到block a和block b所在的block stack，然后只把a上面的所有block还原到初始stack（的栈顶位置），而b所在的stack不动。最后把a弹出，压在b所在的stack栈顶。
pile a onto b:
先找到block a和block b所在的block stack，然后只把b上面的所有block还原到出事stack（的栈顶位置），而a所在的stack不动。最后把a以及其上一直到栈顶的所有栈元素，保持相对位置不变，一起被截取然后放到b（所在的stack栈顶）上面。
pile a over b:
先找到block a和block b所在的block stack，然后直接把a以及其上一直到栈顶的所有栈元素，保持相对位置不便，一起被截取然后放到b（所在的stack栈顶）上面。
quit:
读到这条指令，算法直接结束。
3. AC Code
1 #include <iostream> 2 #include <stdio.h> 3 #include <stack> 4 #include <iomanip> 5 #define N 30 6 using namespace std; 7 8 int block_num; // 积木数目 9 10 int get_block_position(stack<int> block, int a) { 11 stack<int> q = block; 12 while(!q.empty()) { 13 if(a == q.top()) return 1; 14 q.pop(); 15 } 16 return 0; 17 } 18 void move_onto(stack<int> blocks[], int block_a, int block_b) { 19 if(block_a == block_b) return; 20 21 for(int i = 0; i < block_num; i ++) { 22 if(get_block_position(blocks[i], block_a)) { 23 while(!blocks[i].empty() && block_a != blocks[i].top()) { 24 blocks[blocks[i].top()].push(blocks[i].top()); 25 blocks[i].pop(); 26 } 27 for(int j = 0; i < block_num; j ++) { 28 if(get_block_position(blocks[j], block_b)) { 29 if(i == j) return; 30 while(!blocks[j].empty() && block_b != blocks[j].top()) { 31 blocks[blocks[j].top()].push(blocks[j].top()); 32 blocks[j].pop(); 33 } 34 blocks[j].push(blocks[i].top()); 35 blocks[i].pop(); 36 break; 37 } 38 } 39 break; 40 } 41 } 42 43 } 44 45 void move_over(stack<int> blocks[], int block_a, int block_b) { 46 if(block_a == block_b) return; 47 48 for(int i = 0; i < block_num; i ++) { 49 if(get_block_position(blocks[i], block_a)) { 50 while(!blocks[i].empty() && block_a != blocks[i].top()) { 51 blocks[blocks[i].top()].push(blocks[i].top()); 52 blocks[i].pop(); 53 } 54 for(int j = 0; i < block_num; j ++) { 55 if(get_block_position(blocks[j], block_b)) { 56 if(i == j) return; 57 blocks[j].push(blocks[i].top()); 58 blocks[i].pop(); 59 break; 60 } 61 } 62 break; 63 } 64 } 65 } 66 67 void pile_onto(stack<int> blocks[], int block_a, int block_b) { 68 if(block_a == block_b) return; 69 70 for(int i = 0; i < block_num; i ++) { 71 if(get_block_position(blocks[i], block_b)) { 72 while(!blocks[i].empty() && block_b != blocks[i].top()) { 73 blocks[blocks[i].top()].push(blocks[i].top()); 74 blocks[i].pop(); 75 } 76 for(int j = 0; i < block_num; j ++) { 77 if(get_block_position(blocks[j], block_a)) { 78 if(i == j) return; 79 stack<int> q; 80 while(!blocks[i].empty() && block_a != blocks[j].top()) { 81 q.push(blocks[j].top()); 82 blocks[j].pop(); 83 } 84 q.push(blocks[j].top()); 85 blocks[j].pop(); 86 87 while(!q.empty()) { 88 blocks[i].push(q.top()); 89 q.pop(); 90 } 91 break; 92 } 93 } 94 break; 95 } 96 } 97 } 98 99 void pile_over(stack<int> blocks[],int block_a, int block_b) {100 if(block_a == block_b) return;101 102 for(int i = 0; i < block_num; i ++) {103 if(get_block_position(blocks[i], block_b)) {104 105 for(int j = 0; i < block_num; j ++) { 106 if(get_block_position(blocks[j], block_a)) {107 if(i == j) return;108 stack<int> q;109 while(!blocks[i].empty() && block_a != blocks[j].top()) {110 q.push(blocks[j].top());111 blocks[j].pop();112 }113 q.push(blocks[j].top());114 blocks[j].pop();115 116 while(!q.empty()) {117 blocks[i].push(q.top());118 q.pop();119 }120 break;121 } 122 }123 break; 124 }125 }126 }127 128 void output(stack<int> blocks[]) {129 for(int i = 0; i < block_num; i ++) {130 cout <<setw(2)<< i << ": ";131 stack<int> q;132 while(!blocks[i].empty()) {133 q.push(blocks[i].top());134 blocks[i].pop();135 }136 while(!q.empty()) {137 cout << " ";138 cout << q.top();139 q.pop();140 }141 cout << endl;142 }143 }144 int main() {145 146 string commend_1; // 命令147 string commend_2;148 int block_a;149 int block_b;150 // freopen("in.txt", "r", stdin);151 cin >> block_num;152 stack<int> blocks[N];153 154 155 for(int i = 0; i < block_num; i ++) {156 blocks[i].push(i);157 }158 159 while(cin >> commend_1 && commend_1 != "quit") {160 if(commend_1 == "move") {161 cin >> block_a;162 cin >> commend_2;163 if(commend_2 == "onto") {164 cin >> block_b;165 move_onto(blocks, block_a, block_b);166 }else if(commend_2 == "over"){167 cin >> block_b;168 move_over(blocks, block_a, block_b);169 } 170 }else if(commend_1 == "pile") {171 cin >> block_a;172 cin >> commend_2;173 if(commend_2 == "onto") {174 cin >> block_b;175 pile_onto(blocks, block_a, block_b);176 }else if(commend_2 == "over"){177 cin >> block_b;178 pile_over(blocks,block_a, block_b);179 }180 }181 }182 183 output(blocks);184 return 0; 185 }
USTC OJ — 1004 Block world （数据结构stack，简单题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。