算法习题---5.2木块问题（UVa101）

一：题目

输入n，得到编号为0~n-1的木块，分别摆放在顺序排列编号为0~n-1的位置。现对这些木块进行操作，操作分为四种。

1、move a onto b：把木块a、b上的木块放回各自的原位，再把a放到b上；

2、move a over b：把a上的木块放回各自的原位，再把a发到含b的堆上；

3、pile a onto b：把b上的木块放回各自的原位，再把a连同a上的木块移到b上；

4、pile a over b：把a连同a上木块移到含b的堆上。

当输入quit时，结束操作并输出0~n-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

（二）样例输出

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

二：代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define MAX 30
vector<int> column[MAX];
int num;
int a_n, a_m, b_n, b_m;

通过引用返回行列数

void find_col(int a,int &n,int &m)
{
    for (int i = 0; i < num; i++)
        for (int j = 0; j < column[i].size();j++)
            if (column[i][j] == a)
                n = i, m = j;
}

返回该操作数所在列数

//返回所操作列数
int PushOldPos(int a)
{
    int n, m;
    find_col(a, n, m);
    while (m < column[n].size()-1)
    {
        int i = column[n][++m];
        column[i].push_back(i);
    }
    return n;
}

四个操作函数

void MoveAOntoB(int a, int b)
{
    //将a上面的数据全部归位
    a_n = PushOldPos(a);
    //将b上面的数据全部归位
    b_n = PushOldPos(b);

    //将a放入b上
    column[b_n].push_back(column[a_n].back());
    column[a_n].pop_back();
}

void MoveAOverB(int a, int b)
{
    //将a上面的数据全部归位
    a_n = PushOldPos(a);

    //将a放入b上
    column[b_n].push_back(column[a_n].back());
    column[a_n].pop_back();
}
void PileAOntoB(int a, int b)
{
    //将b全部归位
    b_n = PushOldPos(b);

    for (int i = a_m; i < column[a_n].size(); i++)
        column[b_n].push_back(column[a_n][i]);

    column[a_n].resize(a_m);
}

void PileAOverB(int a, int b)
{
    for (int i = a_m; i < column[a_n].size(); i++)
        column[b_n].push_back(column[a_n][i]);

    column[a_n].resize(a_m);
}

打印函数

void PrintAllCol()
{
    //进行打印
    for (int i = 0; i < num;i++)
    {
        cout << i << ": ";
        for (vector<int>::iterator iter = column[i].begin(); iter != column[i].end(); iter++)
            cout << *iter << " ";
        cout << endl;
    }
}

主函数

int main()
{
    freopen("data5_2.in", "r", stdin);
    freopen("data5_2.out", "w", stdout);
    
    string a_str, b_str;
    int a,b;
    cin >> num; //获取总的盒子数

    //初始化向量
    for (int i = 0; i < num; i++)
        column[i].push_back(i);

    //获取命令进行处理
    while (true)
    {
        cin >> a_str;
        if (a_str == "quit")
            break;
        cin >> a >> b_str >> b;

        find_col(b, b_n, b_m);
        find_col(a, a_n, a_m);　　//先找到两个数各自的行列数

        if (a_n == b_n)　　//如果在同一行，则操作失效
            continue;
        if (a_str == "move")
            if (b_str == "over")
                MoveAOverB(a, b);
            else
                MoveAOntoB(a, b);
        else
            if (b_str == "over")
                PileAOverB(a, b);
            else
                PileAOntoB(a, b);
    }

    PrintAllCol();

    freopen("CON", "r", stdin);
    freopen("CON", "w", stdout);
    return 0;
}