You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

94 lines
3.5 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
//https://blog.csdn.net/weixin_30516243/article/details/95800585
//https://www.luogu.com.cn/problemnew/solution/UVA101?page=2
/**
总的来说就是碰到move就要把a上面的全部放回原处。
如果碰到 onto 就要把b上面的全部放到原处。 因为move是只移动a一个,
所以a上面的要归位,而pile是移一堆,所以不用。
onto是要和b贴在一起,所以b上面的要归位,而over是上方,不需要直接接触,
所以不用。。思路就是用栈来模拟,一开始就是n个栈。每个栈里都是一个元素,然后按照指令移,
在这个栈里pop()掉它,在另一个栈里push()进去。。 分四种情况来做移动,
每种情况处理方式不一样。要注意如果是一堆移过去,因为还是要按照这个顺序,
多以要先把这一堆放到另一个数组再按顺序j进去。 模拟完输出即可。。
*/
const int maxn = 30;
int n;
vector<int> pile[maxn]; //每个pile[i]是一个vector
//找木块a所在的pile和height以引用的形式返回调用者
void find_block(int a, int &p, int &h) {
for (p = 0; p < n; p++) //挨个堆去查找
for (h = 0; h < pile[p].size(); h++) //进入某个堆后,一个个开始查找,从下向上找
//如果找到返回所在的堆p和高度h,通过&p和&h可以直接将数据修改后返回到主函数
if (pile[p][h] == a)
return;
}
//把第p堆高度为h的木块上方的所有木块移回原位
void clear_above(int p, int h) {
//找到p堆h高度以上的所有木块
for (int i = h + 1; i < pile[p].size(); i++) {
int b = pile[p][i];
pile[b].push_back(b); //把木块b放回原位堆
}
//更改大小相当于删除了vector里面多余的元素
pile[p].resize(h + 1); //pile只应保留下标0~h的元素
}
//把第p堆高度为h及其上方的木块整体移动到p2堆的顶部
void pile_onto(int p, int h, int p2) {
for (int i = h; i < pile[p].size(); i++)
pile[p2].push_back(pile[p][i]);
pile[p].resize(h);
}
//输出结果
void print() {
for(int i = 0; i < n; i++) {
printf("%d:", i);
for(int j = 0; j < pile[i].size(); j++)
printf(" %d", pile[i][j]);
printf("\n");
}
}
int main() {
int a, b;
cin >> n;
string s1, s2;
//共n堆每堆1个计为i号林块0<=i<n),所以有两个概念,
// 一个是第几堆,一个是第几块,最开始是一样的数字,即 i=1时第1堆里放着第1块木块
//但是随着移动变化,堆不变,但块会被移走或被其它林块盖上。
for (int i = 0; i < n; i++)
pile[i].push_back(i);
//读入命令
while (cin >> s1 >> a >> s2 >> b) {
int pa, pb, ha, hb;
//pa-->查找现在a木块存在于哪一堆内
//ha-->a木块所在的高度即索引号
find_block(a, pa, ha);
//同上
find_block(b, pb, hb);
//如果同一堆就不能动了,非法指令
if (pa == pb)
continue; //非法指令
//下面开始把共有的部分进行了抽象,节约代码
if (s2 == "onto")
clear_above(pb, hb);
if (s1 == "move")
clear_above(pa, ha);
pile_onto(pa, ha, pb);
}
//输出结果
print();
return 0;
}