【UVA - 101】The Blocks Problem（vector+模拟）

The Blocks Problem

Descriptions:(英语就不说了，直接上翻译吧)

初始时从左到右有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在同一堆)，应当忽略。

输入

输入由1个整数n开始开始，该整数独占一行，表示积木世界中的积木数量。你可以假定0 < n < 25。从积木数量值的下一行开始是一系列的命令，每条命令独占一行。你的程序要处理所有的命令直到输入退出命令。你可以假定所有的命令都按上文所示的格式给出。不会出现语法错误的命令。

输出

以积木世界的最终状态作为输出。每一个原始积木的位置i（0 ≤ i < n，n为积木数量）后面都要紧跟一个冒号。
如果至少有一个积木在该位置上，冒号后面都要紧跟一个空格，然后是该位置上所有积木编号的序列。每2个积木的编号之间以一个空格隔开。行尾不能出现多余的空格。
每个积木位置独占一行（即第一行输入的n，对应输出n行数据）。
样例输入

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

样例输出

0: 0

1: 1 9 2 4

2:

3: 3

4:

5: 5 8 7 6

6:

7:

8:

9:

题目链接：https://vjudge.net/problem/UVA-101

按照题意模拟一遍即可，因为不知道每堆有几个木块，用vector即可

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define mod 1000000007

#define ll long long

#define INF 0x3f3f3f3f

#define ME0(x) memset(x,0,sizeof(x))

using namespace std;

vector<int> v[];

int n;

//找到所在位置，所在高度

void FindBlock(int a,int& p,int& h)//返回p,h的地址

{

    for(p=; p<n; p++)

        for(h=; h<v[p].size(); h++)

            if(v[p][h]==a)

                return;

}

//把第p堆上的第h个以上的木块还原

void MoveBack(int p,int h)

{

    for(int i=h+; i<v[p].size(); i++)

    {

        int t=v[p][i];

        v[t].push_back(t);

    }

    v[p].resize(h+);

}

//把p1堆上的包括h1的木块按顺序移动到p2上

void MoveOn(int p1,int h1,int p2)

{

    for(int i=h1; i<v[p1].size(); i++)

    {

        v[p2].push_back(v[p1][i]);

    }

    v[p1].resize(h1);

}

//输出格式

void Cout()

{

    for(int i=; i<n; i++)

    {

        printf("%d:",i);

        for(int j=; j<v[i].size(); j++)

        {

            printf(" %d",v[i][j]);

        }

        cout<<endl;

    }

}

int main()

{

    cin>>n;

    for(int i=; i<n; i++)

        v[i].push_back(i);

    int a,b;

    string s1,s2;

    while(cin>>s1)

    {

        if(s1=="quit")

            break;

        cin>>a>>s2>>b;

        int pa,pb,ha,hb;

        FindBlock(a,pa,ha);

        FindBlock(b,pb,hb);

        if(pa==pb)

            continue;

        if(s1=="move")

            MoveBack(pa,ha);

        if(s2=="onto")

            MoveBack(pb,hb);

        MoveOn(pa,ha,pb);

    }

    Cout();

}

巴特西

【UVA - 101】The Blocks Problem（vector+模拟）

The Blocks Problem

最新文章

热门文章