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