Uva The Blocks problem——vector的应用——蒟蒻学习刘大爷（详解）

题目传送门

文章目录

题意：
分析：
技巧：
实际分析

题意：

从左到右有n个木块，编号为0~n-1 ，要求模拟一下四种操作（a，b是木块的编号）

1move a onto b：把a和b上方的木块全部归位，然后把a摞在b上面。

2move a over b：把a上方的木块全部归位，然后把a放在b所在木块堆的顶部。

3pile a onto b：把b及上面的木块整体摞在b所偶在木块堆的顶部，

4pile a over b：把a及上面的木块整体摞在b所在木块堆的顶部。
所有操做结束后输出每个位置的木块列表，按照从底部到顶部的顺序排列

分析：

每一个木块堆的高度不确定，所以用vector来保存比较合适，而木块堆的个数不超过n，而且每个堆的木块量不超过n，0<n<25,,
适合用vector
当然也可以用一个二维数组，这里相当于是用vetcor来实现了二维数组

技巧：

这里有四个操作，我们需要提取他们共同的部分，编写成一个功能函数
这样既可以简化代码，也可以减少错误

实际分析

这里的四个操作，我们提取出两大类
1将在某个堆的某个木块上的的全部木块归位
2将某个堆的某个木块及其以上的木块全部移动到另一个堆的顶端，
这里包括了这个木块上有或者没有其他木块的两种情况
3在执行1，2前，我们需要找到输入的a,b两个木块，这时候所在的堆的下标还有高度

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
const int maxn = 30;
vector<int> pile[maxn];//木块堆的二维数组

//找到元素x所在的堆和高度,以引用的形式返回调用者
void find_blocks(int x,int &p ,int &h )
{
    for(p=0;p<n;p++)
    {
        for( h=0;h<pile[p].size();h++)
        {
            if(pile[p][h]==x ) return;//找到后x直接返回，此时将p和h的值传回去
        }
    }
}
//把木块X上的木块全部归位
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);
    }
    pile[p].resize(h+1);//X所在的堆现在只有h+1个木块
}
//把p1堆的高度为h的及其以上的木块移动到p2的顶部
void blocks_move(int p1,int h,int p2)
{
    for(int i=h;i<pile[p1].size();i++)
    {
        int x = pile[p1][i];
        pile[p2].push_back(x);
    }
    pile[p1].resize(h);//这个时候p1堆里只有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;
    cin>>n;
    string s1,s2;
    for(int i=0;i<n;i++) pile[i].push_back(i);//在第i堆放上木块i
    while(cin>>s1&&s1!="quit")
    {
        //cout<<"a"<<endl;
        cin>>a>>s2>>b;
        int pa,pb,ha,hb;
        find_blocks(a,pa,ha);//找到元素所在的堆和高度
        find_blocks(b,pb,hb);
        //现在pa,ha的值已经改变
        if(pa == pb) continue;//a=b这种情况，当然不能继续
        if(s2 == "onto")  clear_above(pb ,hb );
        if(s1 =="move") clear_above(pa ,ha);
        blocks_move(pa,ha,pb);//把a及其以上的木块移动到b所在堆的顶部

    }
    print();
    return 0;
}