点击这里访问该问题的原链接。
这个问题的主要步骤是读取操作中的信息,然后执行相应的操作。最重要的是如何设计数据结构。 数据结构的设计方法有多重多样,这里采用了一个包含25个元素的数组(因为至多25个块),代表25个位置,每个元素是一个vector,里面存放了该位置上面所有的块。 这里的操作可以分解为三种,一种是找到某一个块现在在什么位置,另一种是把一个位置上某一个块上面的块全部归位,另一种是把一个位置上的所有块移到另一个位置上。
(所有的指令基本就是这三种操作的组合)
所以基本上需要三个主要的函数
1. 找到某一个块现在的位置,需要返回它现在在25个位置中的哪个位置,以及它是这个位置上从下往上数第几个块(也就是他的高度)。
2. 把一个位置上某一个块上面的块全部归位。
3. 把一个位置上的所有块移到另一个位置上。
对于第一个操作,可以简单的通过遍历得到,遍历25个位置上的所有块,直到某一个块就是我们要找的块,可以用引用类型返回它的位置和高度。 对于第二个操作,可以先找到这个块的位置,然后把上面的所有块归位,然后重置这个vector的大小。 对于第三个操作,假如是A上的所有块移到B上,可以先找到B所在的位置和A所在的位置和高度,把A高度上面的所有块移动到B上(pushback就可以),然后重置两个vector的大小。 基本函数实现后,只需要在main中循环读取指令,分解出所需要进行的操作,然后执行基本函数就好。 完整的代码如下:
#include<iostream> #include<vector> #include<string> using namespace std; int BlockNum = 0; vector<int> Blocks[25]; void FindBLock(int blocknum, int& blockpile, int& height) { for (blockpile = 0; blockpile < BlockNum; blockpile++) { for(height = 0;height<Blocks[blockpile].size();height++) { if (Blocks[blockpile][height] == blocknum) return; } } } void Homing(int blockpile,int height) { int i; int temp; for (i = height+1; i < Blocks[blockpile].size(); i++) { temp = Blocks[blockpile][i]; Blocks[temp].push_back(temp); } Blocks[blockpile].resize(height+1); } void moveAoverB(int blockpileA, int blockpileB, int heightA) { int i; for (i = heightA; i < Blocks[blockpileA].size(); i++) { Blocks[blockpileB].push_back(Blocks[blockpileA][i]); } Blocks[blockpileA].resize(heightA); } int main() { int i = 0; string man1, man2; int block1, block2; cin >> BlockNum; int pile1, pile2, height1, height2; while (i < BlockNum) { Blocks[i].push_back(i); i++; } i = 0; while (true) { cin >> man1; if (man1 != "move" && man1 != "pile") break; cin >> block1 >> man2 >> block2; FindBLock(block1, pile1, height1); FindBLock(block2, pile2, height2); if (pile1 == pile2) continue; if (man1 == "move") { Homing(pile1, height1); } if (man2 == "onto") { Homing(pile2, height2); } moveAoverB(pile1, pile2, height1); } for (i = 0; i < BlockNum; i++) { cout << i << ": "; for (int j = 0; j < Blocks[i].size(); j++) { cout <<Blocks[i][j]<<' '; } cout << endl; } return 0; }