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

### 题目描述

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

# 【题目描述】

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的命令都是非法的。所有非法的命令都要忽略，且不能对当前积木的状态产生作用。

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