题解 P1242 【新汉诺塔】
Starria的脑残粉
2017-06-15 11:32:16
既然没有c++的题解那我就写一发吧。。
思路其实很简单，优先保证较大的到达，（把其他较小的先移到另一个根柱子上。。处理一下细节就可以了，显然成立的是不会有冗余的操作
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,x,f1[100],f2[100],ans,xx;//f1为盘子的当前状态，f2为终止状态
void dfs(int d,int x,int y,bool kk){//kk表示当前是否是处理这个盘子的时候
int z=1;while (x==z||z==y)z++;
if (x==y){//不需要移动
if (d>1)dfs(d-1,f1[d-1],kk?f2[d-1]:y,kk&&true);
return;
}
if (d>1)dfs(d-1,f1[d-1],z,false);
cout<<"move "<<d<<" from "<<char(x+'A'-1)<<" to "<<char(y+'A'-1)<<endl,ans++;
f1[d]=y;
if (d>1)dfs(d-1,f1[d-1],kk?f2[d-1]:y,kk&&true);//当kk为真时大于等于当前的盘子已经处理完毕（处理剩余的盘子
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
cin>>x;for (int i=1;i<=x;i++)cin>>xx,f1[xx]=1;
cin>>x;for (int i=1;i<=x;i++)cin>>xx,f1[xx]=2;
cin>>x;for (int i=1;i<=x;i++)cin>>xx,f1[xx]=3;
cin>>x;for (int i=1;i<=x;i++)cin>>xx,f2[xx]=1;
cin>>x;for (int i=1;i<=x;i++)cin>>xx,f2[xx]=2;
cin>>x;for (int i=1;i<=x;i++)cin>>xx,f2[xx]=3;
dfs(n,f1[n],f2[n],true);
cout<<ans<<endl;
}
```