洛谷-UVA101 The Blocks Problem-蒲公英云

洛谷-UVA101 The Blocks Problem

输入格式

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;
}