洛谷-UVA101 The Blocks Problem

爱被打了一巴掌 2023-05-31 03:11 15阅读 0赞

## 输入格式 ##

![format_png][]

## 输出格式 ##

![format_png 1][]

## 题意翻译 ##

初始时从左到右有n个木块，编号为0~n-1,要求实现下列四种操作:

*  move a onto b: 把a和b上方的木块全部放回初始的位置，然后把a放到b上面
 *  move a over b: 把a上方的木块全部放回初始的位置，然后把a放在b所在木块堆的最上方
 *  pile a onto b: 把b上方的木块部放回初始的位置，然后把a和a上面所有的木块整体放到b上面
 *  pile a over b: 把a和a上面所有的木块整体放在b所在木块堆的最上方

一组数据的结束标志为"quit"，如果有非法指令(a和b在同一堆)，应当忽略。

输出:所有操作输入完毕后，从左到右，从下到上输出每个位置的木块编号。 感谢U27114 jxdql2001 提供的翻译

## 输入输出样例  ##

**输入 \#1**复制

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

**输出 \#1**复制

0: 0
    1: 1 9 2 4
    2:
    3: 3
    4:
    5: 5 8 7 6
    6:
    7:
    8:
    9:

**难点：能读懂题目，但找不到一般性规律！**  
发现4种操作最后的操作都有**共通点**：a和a上方的木块都放在b堆上。  
另外:pile和over其实没有用！！  
找到此共通点后，其实就是.  
move a：a上方的归位  
onto b：b上方的归为  
总结而来就是两步操作：归位 和 移动  
注：隐藏的条件有 木块在同堆则跳过此操作。

#include<bits/stdc++.h>
    using namespace std;
    
    vector<int> block[30]; //一维固定，二维不固定 
    int n;//n个块 
    
    //初始化 
    void init()
    {
        cin>>n;
        for(int i=0;i<n;i++)
            block[i].push_back(i);
    }
    
    //找位置(x：待归为的编号，p：横坐标，h：纵坐标)
    void loc(int x,int &p,int &h)
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<block[i].size();j++)
            {
                if(block[i][j]==x)
                {
                    p=i;
                    h=j;
                }
            }
    }
    
    //归位操作 (p：横坐标，h：纵坐标)
    //p堆>h的所有块归位
    void goback(int p,int h)
    {
        for(int i=h+1;i<block[p].size();i++)
        {
            int k=block[p][i];
            block[k].push_back(k);
        }
        block[p].resize(h+1);//重置大小（清空操作） 
    }
    
    //p堆>=h的所有块移动到q之上
    void moveall(int p,int h,int q)
    {
        for(int i=h;i<block[p].size();i++)
        {
            int k=block[p][i];
            block[q].push_back(k);
        }
        block[p].resize(h);//重置大小
    }
    
    
    void solve()
    {
        int a,b;
        string s1,s2;
        while(cin>>s1)
        {
            if(s1=="quit")
                break;
            cin>>a>>s2>>b;
            int ap=0,ah=0,bp=0,bh=0;
            loc(a,ap,ah);
            loc(b,bp,bh);
            //如果a，b在同一堆，则忽略 
            if(ap==bp)
            	continue;
            if(s1=="move")//a归位
                goback(ap,ah);
            if(s2=="onto")//b归位
                goback(bp,bh);
            moveall(ap,ah,bp);
        }
    }
    
    void print()
    {
        for(int i=0;i<n;i++)
        {
            cout<<i<<":";
            for(int j=0;j<block[i].size();j++)
                cout<<" "<<block[i][j]<<endl;
        }
    }
    
    int main()
    {
        init();
        solve();
        print();
        return 0;
    }

[format_png]: /images/20230531/4e7bf6b3d3f44943bd4678e9d185277c.png
[format_png 1]: /images/20230531/9970c093c39b46db9e3f865b9f3ce70a.png