题解 P1242 【新汉诺塔】

2017-06-15 11:32:16


既然没有c++的题解那我就写一发吧。。

思路其实很简单,优先保证较大的到达,(把其他较小的先移到另一个根柱子上。。处理一下细节就可以了,显然成立的是不会有冗余的操作

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