Skip to content

14096: 【原4096】小居居搬箱子

题目

题目描述

author: kikyou 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4096

【题目描述】

黑爷家有一只小居居,喜欢玩搬箱子的游戏。有一天,黑爷写完了数据结构大作业,决定看看小居居到底是怎么搬箱子的。

黑爷家一共有N个箱子,箱子的编号是0-base的。最开始从第0个箱子开始,按照编号递增的位置,从左到右放成一行。小居居的操作比较简单,只有下面这四种:

move a over b,把a上面的箱子放到初始位置,并把a放到b箱子的最上方; move a onto b,把a和b上面的箱子放回初始位置,并把a放到b上面; pile a over b,把a和a上面的箱子一起放到b的最上方; pile a onto b,把b上面的箱子放回初始位置,然后把a和a上面的箱子一起放到b上面。 当a = b或a和b处在同一摞时,任何企图操作a和b的命令都是非法的。所有非法的命令都要忽略,且不能对当前积木的状态产生作用。

黑爷于是写了个程序来输出最后每个位置的箱子,但是bug太多了黑爷查不出来。黑爷请你帮他debug,但是你觉得太麻烦了,于是决定先自己写一份。

【输入要求】

输入由1个整数N开始开始,该整数独占一行,0<N<25。 接下来是一系列的小居居的行动记录,每条记录独占一行。所有的记录都按照上面的形式给出。最后“quit”代表小居居行动结束。

【输出要求】

以箱子的最终状态作为输出。每一个原始箱子的位置i(0 ≤ i < N)后面都要紧跟一个冒号。

如果至少有一个箱子在该位置上,冒号后面都要紧跟一个空格,然后是该位置上所有箱子编号的序列。每2个箱子的编号之间以一个空格隔开。行尾不能出现多余的空格。 每个位置独占一行,一共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:

FineArtz's solution

/* 小居居搬箱子 */
#include <iostream>
#include <cstring>
using namespace std;

int a[26][26] = {0};
int place[26] = {0}, sum[26] = {0};
int n;

void remove(int x){
    int p = place[x];
    int i = 1;
    while (a[p][i] != x)
        ++i;
    for (int j = i + 1; j <= sum[p]; ++j){
        int t = a[p][j];
        a[t][1] = t;
        place[t] = t;
        sum[t] = 1;
        a[p][j] = 0;
    }
    sum[p] = i;
}

void moveover(int x, int y){
    int p = place[x], q = place[y];
    remove(x);
    a[q][++sum[q]] = x;
    a[p][sum[p]--] = 0;
    place[x] = q;
}

void moveonto(int x, int y){
    int p = place[x], q = place[y];
    remove(x);
    remove(y);
    a[q][++sum[q]] = x;
    a[p][sum[p]--] = 0;
    place[x] = q;
}

void pileover(int x, int y){
    int p = place[x], q = place[y];
    int i = 1;
    while (a[p][i] != x)
        ++i;
    for (int j = i; j <= sum[p]; ++j){
        a[q][++sum[q]] = a[p][j];
        place[a[p][j]] = q;
        a[p][j] = 0;
    }
    sum[p] = i - 1;
}

void pileonto(int x, int y){
    int p = place[x], q = place[y];
    remove(y);
    int i = 1;
    while (a[p][i] != x)
        ++i;
    for (int j = i; j <= sum[p]; ++j){
        a[q][++sum[q]] = a[p][j];
        place[a[p][j]] = q;
        a[p][j] = 0;
    }
    sum[p] = i - 1;
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i){
        a[i][1] = i;
        place[i] = i;
        sum[i] = 1;
    }
    char s1[10], s2[10];
    int x, y;
    cin >> s1;
    while (s1[0] != 'q'){
        cin >> x >> s2 >> y;
        ++x, ++y;
        if (place[x] == place[y]){
            cin >> s1;
            continue;
        }
        if (s1[0] == 'm'){
            if (s2[1] == 'v')
                moveover(x, y);
            else
                moveonto(x, y);
        }
        else{
            if (s2[1] == 'v')
                pileover(x, y);
            else
                pileonto(x, y);
        }
        cin >> s1;
    }
    for (int i = 0; i < n; ++i){
        cout << i << ":";
        for (int j = 1; j <= sum[i + 1]; ++j)
            cout << ' ' << a[i + 1][j] - 1;
        cout << endl;
    }
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstring"
#include "cstdio"
using namespace std;

int box[25][25] = { 0 };
int boxx[25] = { 0 }, boxy[25] = { 0 };
int box_num[25] = { 0 };

int main() {
    int N;
    scanf("%d", &N);

    //初始化
    for (int i = 0; i < N; ++i) {
        box[i][0] = i;
        boxx[i] = i;
        boxy[i] = 0;
        box_num[i] = 1;
    }

    while (true) {
        char opt1[20], opt2[20];
        int a, b;
        scanf("%s", opt1);
        if (strcmp(opt1, "quit") == 0)
            break;
        scanf("%d %s %d", &a, opt2, &b);
        if (a == b || boxx[a] == boxx[b])
            continue;
        if (strcmp(opt1, "move") == 0 && strcmp(opt2, "over") == 0) {
            for (int i = boxy[a] + 1; i < box_num[boxx[a]]; ++i) {
                auto temp = box[boxx[a]][i];
                box[temp][0] = temp;
                box[boxx[a]][i] = 0;
                boxx[temp] = temp;
                boxy[temp] = 0;
                box_num[temp] = 1;
            }
            box[boxx[a]][boxy[a]] = 0;
            box_num[boxx[a]] = boxy[a];
            //移动
            box[boxx[b]][box_num[boxx[b]]] = a;
            boxx[a] = boxx[b];
            boxy[a] = box_num[boxx[b]]++;
        }
        else if (strcmp(opt1, "move") == 0 && strcmp(opt2, "onto") == 0) {
            for (int i = boxy[a] + 1; i < box_num[boxx[a]]; ++i) {
                auto temp = box[boxx[a]][i];
                box[temp][0] = temp;
                box[boxx[a]][i] = 0;
                boxx[temp] = temp;
                boxy[temp] = 0;
                box_num[temp] = 1;
            }
            for (int i = boxy[b] + 1; i < box_num[boxx[b]]; ++i) {
                auto temp = box[boxx[b]][i];
                box[temp][0] = temp;
                box[boxx[b]][i] = 0;
                boxx[temp] = temp;
                boxy[temp] = 0;
                box_num[temp] = 1;
            }
            box[boxx[a]][boxy[a]] = 0;
            box_num[boxx[a]] = boxy[a];
            box_num[boxx[b]] = boxy[b] + 1;
            //移动
            box[boxx[b]][box_num[boxx[b]]] = a;
            boxx[a] = boxx[b];
            boxy[a] = box_num[boxx[b]]++;
        }
        else if (strcmp(opt1, "pile") == 0 && strcmp(opt2, "over") == 0) {
            //移动
            auto ori_x = boxx[a], ori_y = boxy[a], ori_num = box_num[boxx[a]];
            for (int i = ori_y; i < ori_num; ++i) {
                auto temp = box[ori_x][i];
                box[boxx[b]][box_num[boxx[b]]++] = temp;
                box[ori_x][i] = 0;
                --box_num[ori_x];
                boxx[temp] = boxx[b];
                boxy[temp] = box_num[boxx[b]] - 1;
            }
        }
        else if (strcmp(opt1, "pile") == 0 && strcmp(opt2, "onto") == 0) {
            for (int i = boxy[b] + 1; i < box_num[boxx[b]]; ++i) {
                auto temp = box[boxx[b]][i];
                box[temp][0] = temp;
                box[boxx[b]][i] = 0;
                boxx[temp] = temp;
                boxy[temp] = 0;
                box_num[temp] = 1;
            }
            box_num[boxx[b]] = boxy[b] + 1;
            //移动
            auto ori_x = boxx[a], ori_y = boxy[a], ori_num = box_num[boxx[a]];
            for (int i = ori_y; i < ori_num; ++i) {
                auto temp = box[ori_x][i];
                box[boxx[b]][box_num[boxx[b]]++] = temp;
                box[ori_x][i] = 0;
                --box_num[ori_x];
                boxx[temp] = boxx[b];
                boxy[temp] = box_num[boxx[b]] - 1;
            }
        }
    }

    for (int i = 0; i < N; ++i) {
        cout << i << ":";
        for (int j = 0; j < box_num[i]; ++j)
            cout << " " << box[i][j];
        cout << endl;
    }

    return 0;
}

Neight99's solution

#include <cstring>
#include <iostream>

using namespace std;

const int maxN = 25 + 10;

struct Node {
    int data;
    Node *next, *prev;

    Node(int d = 0, Node *nxt = 0, Node *pev = 0)
        : data(d), next(nxt), prev(pev) {}
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Node *boxNow[maxN] = {0}, *boxes[maxN] = {0};
    char order1[10], order2[10];
    int N, x, y;
    cin >> N;

    for (int i = 0; i < N; i++) {
        boxes[i] = new Node(i);
        boxNow[i] = boxes[i];
    }

    while (1) {
        cin >> order1;
        if (!strcmp(order1, "quit")) {
            break;
        } else {
            bool flag = 0;

            cin >> x >> order2 >> y;
            Node *temp1 = boxes[x];
            while (temp1 != 0) {
                if (temp1->data == y) {
                    flag = 1;
                    break;
                }
                temp1 = temp1->next;
            }
            temp1 = boxes[y];
            while (temp1 != 0 && !flag) {
                if (temp1->data == x) {
                    flag = 1;
                    break;
                }
                temp1 = temp1->next;
            }
            if (flag) {
                continue;
            }

            if (!strcmp(order1, "move") && !strcmp(order2, "over")) {
                Node *p = boxes[x]->next, *q;
                while (p != 0) {
                    q = p->next;
                    p->prev->next = 0;
                    p->prev = 0;
                    boxNow[p->data] = p;
                    p = q;
                }

                p = boxes[y];
                while (p->next != 0) {
                    p = p->next;
                }
                p->next = boxes[x];
                if (boxes[x]->prev != 0) {
                    boxes[x]->prev->next = 0;
                }
                if (boxNow[x] == boxes[x]) {
                    boxNow[x] = 0;
                }
                boxes[x]->prev = p;
            } else if (!strcmp(order1, "move") && !strcmp(order2, "onto")) {
                Node *p = boxes[x]->next, *q;
                while (p != 0) {
                    q = p->next;
                    p->prev->next = 0;
                    p->prev = 0;
                    boxNow[p->data] = p;
                    p = q;
                }
                p = boxes[y]->next;
                while (p != 0) {
                    q = p->next;
                    p->prev->next = 0;
                    p->prev = 0;
                    boxNow[p->data] = p;
                    p = q;
                }

                p = boxes[y];
                p->next = boxes[x];
                if (boxes[x]->prev != 0) {
                    boxes[x]->prev->next = 0;
                }
                if (boxNow[x] == boxes[x]) {
                    boxNow[x] = 0;
                }
                boxes[x]->prev = p;
            } else if (!strcmp(order1, "pile") && !strcmp(order2, "over")) {
                Node *p = boxes[y];
                while (p->next != 0) {
                    p = p->next;
                }
                p->next = boxes[x];
                if (boxes[x]->prev != 0) {
                    boxes[x]->prev->next = 0;
                }
                if (boxNow[x] == boxes[x]) {
                    boxNow[x] = 0;
                }
                boxes[x]->prev = p;
            } else if (!strcmp(order1, "pile") && !strcmp(order2, "onto")) {
                Node *p = boxes[y]->next, *q;
                while (p != 0) {
                    q = p->next;
                    p->prev->next = 0;
                    p->prev = 0;
                    boxNow[p->data] = p;
                    p = q;
                }

                p = boxes[y];
                while (p->next != 0) {
                    p = p->next;
                }
                p->next = boxes[x];
                if (boxes[x]->prev != 0) {
                    boxes[x]->prev->next = 0;
                }
                if (boxNow[x] == boxes[x]) {
                    boxNow[x] = 0;
                }
                boxes[x]->prev = p;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        cout << i << ':';
        Node *p = boxNow[i];
        while (p != 0) {
            cout << ' ' << p->data;
            p = p->next;
        }
        cout << '\n';
    }

    return 0;
}

skyzh's solution

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector <int> box [100];
int N;

void whereis(int b, int& stack, int& pos) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < box[i].size(); j++) {
            if (box[i][j] == b) {
                stack = i;
                pos = j;
                return;
            }
        }
    }
}

void reset_from(int stack, int pos) {
    int _p = box[stack].size() - 1;
    while (_p >= pos) {
        int _b = box[stack][_p];
        box[stack].pop_back();
        box[_b].push_back(_b);
        --_p;
    }
}

void move_from(int from, int pos, int to) {
    int _p = box[from].size() - 1;
    vector <int> tmp;
    while (_p >= pos) {
        int _b = box[from][_p];
        box[from].pop_back();
        tmp.push_back(_b);
        --_p;
    }
    while (tmp.size() > 0) {
        box[to].push_back(tmp[tmp.size() - 1]);
        tmp.pop_back();
    }
}

int main() {
    cin >> N;

    for (int i = 0; i < N; i++) box[i].push_back(i);
    while (true) {
        string cmd, op;
        int op1, op2;
        cin >> cmd;
        if (cmd == "quit") break;
        cin >> op1 >> op >> op2;
        if (cmd == "move") {
            int as, ap, bs, bp;
            whereis(op1, as, ap);
            whereis(op2, bs, bp);
            if (as == bs) continue;
            reset_from(as, ap + 1);
            if (op == "onto") reset_from(bs, bp + 1);
            box[as].pop_back();
            box[bs].push_back(op1);
        }
        if (cmd == "pile") {
            int as, ap, bs, bp;
            whereis(op1, as, ap);
            whereis(op2, bs, bp);
            if (as == bs) continue;
            if (op == "onto") reset_from(bs, bp + 1);
            move_from(as, ap, bs);
        }
    }
    for (int i = 0; i < N; i++) {
        cout << i << ":";
        for (int j = 0; j < box[i].size(); j++) {
            cout << " " << box[i][j];
        }
        cout << endl;
    }
    return 0;
}