P2790 ccj与zrz之积木问题 题解
题目传送门
更好的阅读体验？
思路：
依照题意直接模拟即可，需要注意题目中的坑。特别注意，
（本题解使用自增自减运算符，不懂它们的同学可以先百度）。
代码拆分：
定义：
-
需要记忆
a 和b 在哪一个积木堆里，方便以后寻找。 -
建一个二维数组存积木的详细位置，例如，
ans_{i,j} 表示在编号为i 的积木堆中从下往上数第j 个位置的积木编号。 -
还需要记忆每堆积木的数量，方便以后进行移位操作。
-
定义四个变量存指令信息，两个
int类型 两个string类型（char也行），还需定义积木数n 。
int ans[105][105];//ans存x现在在哪
int num[105];//存x号位积木数量
int vis[105];//记忆i存到了几号位
int a,b,n;
string nw1,nw2;//存指令 初始化：
-
所有积木编号由
0 到n-1 。 -
起初，每个积木都在自己编号的位置上，每堆积木数量都是
1 。
for(int i=0;i<=n-1;i++)//初始化
{
vis[i]=i;//记忆积木位置
ans[i][1]=i;//初始的积木堆上
num[i]=1;//记忆数量
}核心模拟：
-
重点：循环的语句格式为
while(true)，不是for(int i=1;i<=n;i++)！！！ -
遇到
quit时应立刻停止循环。 -
当积木
a 和积木b 在同一堆里时，应当忽略这条指令。 -
寻找 a 和 b 在积木堆中的位置：
- 已经记忆过了。
int x=vis[a];//寻找a在积木中的位置
int y=vis[b];//寻找b在积木中的位置a 上方的木块全部归位:
-
需要归位的有：积木的记忆位置，详细位置。
-
for(int j=num[x];j>=1;j--)//a上方的木块全部归位
{
if(ans[x][j]==a) break;//到a了就停止寻找
num[x]--;//a积木塔上积木数减一
int z=ans[x][j];//计算当前积木堆顶的值
ans[z][++num[z]]=z;//归位
vis[z]=z;//记忆归位
}b 上方的木块全部归位:
- 类比
a 上方积木的归位方法。
for(j=num[y];j>=1;j--)//把b上方的木块全部归位
{
if(ans[y][j]==b) break;
num[y]--;
int z=ans[y][j];
ans[z][++num[z]]=z;
vis[z]=z;
}把 a 移到 b 上面：
- 不要忘了记忆的更改，同时，因为循环结束条件，还要把
a 原来所在的积木堆的积木数减1 。
ans[y][++num[y]]=a;//把a放到b上方
num[x]--;
vis[a]=y;把 a 及上面的木块整体摞在 b 上面：
-
需要先查找
a 记忆里是在从下往上数的第几个积木。 -
在函数内定义变量时值是随机的，需要清零。
-
注意移位方法：整体移位。
int j,p=0,rember=0;
while(ans[x][++p]!=a);//寻找a的位置
for(;p<=num[x];p++)//注意循环的写法
{//把a及上面的木块整体摞在b上面
int z=ans[x][p];
ans[y][++num[y]]=z;
vis[z]=y;
}
num[x]=rember-1;
//现在a原来所在的积木数为
//a原来的位置减1
//因为a已经被移走了 输出：
-
从
0 到n-1 。 -
注意格式：在字符
:后有空格。
for(int i=0;i<=n-1;i++)//按照题意输出，从0到n-1
{
cout<<i<<":";
for(int j=1;j<=num[i];j++)
{
cout<<" "<<ans[i][j];//别忘了:后的空格
}
cout<<endl;//别忘了换行
}完整代码之一：
#include<bits/stdc++.h>//万能头文件
using namespace std;
int ans[105][105];//ans存x现在在哪
int num[105];//存x号位积木数量
int vis[105];//记忆i存到了几号位
int a,b,n;
string nw1,nw2;//存指令
int main()
{
cin>>n;
for(int i=0;i<=n-1;i++)//初始化
{
vis[i]=i;//记忆积木位置
ans[i][1]=i;//初始的积木堆上
num[i]=1;//记忆数量
}
while(true)//注意，是 while(true),while(true),while(true)!!!!
{
cin>>nw1>>a>>nw2>>b;//输入
if(nw1=="quit") break;//遇到quit停止
if(vis[a]==vis[b]) continue;//指令非法
int x=vis[a];//寻找a在积木中的位置
int y=vis[b];//寻找b在积木中的位置
if(nw1=="move"&&nw2=="onto")
{
for(int j=num[x];j>=1;j--)//a上方的木块全部归位
{
if(ans[x][j]==a) break;//到a了就停止寻找
num[x]--;//a积木塔上积木数减一
int z=ans[x][j];//计算当前积木堆顶的值
ans[z][++num[z]]=z;//归位
vis[z]=z;//记忆归位
}
for(int j=num[y];j>=1;j--)//b上方的木块全部归位
{
if(ans[y][j]==b) break;
num[y]--;
int z=ans[y][j];
ans[z][++num[z]]=z;
vis[z]=z;
}
ans[y][++num[y]]=a;//把a放到b上方
num[x]--;
vis[a]=y;
}
if(nw1=="move"&&nw2=="over")
{
for(int j=num[x];j>=1;j--)//把a上方的全部归位
{
if(ans[x][j]==a) break;//同上
num[x]--;
int z=ans[x][j];
ans[z][++num[z]]=z;
vis[z]=z;
}
num[x]--;//同上
ans[y][++num[y]]=a;
vis[a]=y;
}
if(nw1=="pile"&&nw2=="onto")
{
int j,p=0,rember=0;
//主函数内定义变量时值是随机的，需要清零
for(j=num[y];j>=1;j--)//把b上方的木块全部归位
{
if(ans[y][j]==b) break;//同上
num[y]--;
int z=ans[y][j];
ans[z][++num[z]]=z;
vis[z]=z;
}
while(ans[x][++p]!=a);//寻找a的位置
rember=p;//记录a的位置
for(;p<=num[x];p++)//注意循环的写法
{//把a及上面的木块整体摞在b上面
int z=ans[x][p];
ans[y][++num[y]]=z;
vis[z]=y;
}
num[x]=rember-1;
//现在a原来所在的积木数为
//a原来的位置减1
//因为a已经被移走了
}
if(nw1=="pile"&&nw2=="over")
{
int p=0,rember=0;
while(ans[x][++p]!=a);
rember=p;//记录a的位置
for(;p<=num[x];p++)//同上
{
int z=ans[x][p];
ans[y][++num[y]]=z;
vis[z]=y;
}
num[x]=rember-1;//同上
}
}
for(int i=0;i<=n-1;i++)//按照题意输出，从0到n-1
{
cout<<i<<":";
for(int j=1;j<=num[i];j++)
{
cout<<" "<<ans[i][j];//别忘了:后的空格
}
cout<<endl;//别忘了换行
}
return 0;
}另一些代码：
清奇的代码
函数封装代码1
函数封装代码2
还可以点这里下载代码