题解 P1242 【新汉诺塔】

友利奈绪 · 2018-06-06 18:41:26 · 题解

汉诺塔推广到普遍解法，我用的也是dfs，借鉴了题解第一位大佬的做法。不过个人觉得那个bool kk可能有些人不好理解（划掉，可能只有我不理解吧。。。），所以把它单独拆出来写一个DFS_false函数，其大体和dfs相同。 这个题的思路就是对情况进行判断。进入dfs把过过渡柱子z找出来，从最大的盘子开始dfs。如果当前盘子就在目标位置上，那就不用移动，对d-1的盘子进行直接前往它们该去的地方（f2[d-1]）的操作。如果不在，那就得跳入dfs_false函数，先将散乱的其他小盘子通过类似的方法移到过渡柱子上，然后把大盘子移过去，最后进行类似的操作。具体的dfs_false函数思路和普通的汉诺塔问题思路类似，不再赘述。注意当进行完这步操作时d-1的盘子一定是从小到大在过渡柱子上排列的。

上代码，这个题解不过也行，反正是给自己看的……

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int f1[50],f2[50],x,ans=0,xx;
void dfs_false(int d,int x,int y)
{
    if(d==0) return;
    int z=1;
    while(x==z||y==z) z++;
    if(x==y)
    {
        dfs_false(d-1,f1[d-1],y);
        return ;
    }
    else
    {
        dfs_false(d-1,f1[d-1],z);
        cout<<"move"<<' '<<d<<' '<<"from"<<' '<<char(x+'A'-1)<<' '<<"to"<<' '<<char(y+'A'-1)<<endl; ans++;
        f1[d]=y;
        dfs_false(d-1,f1[d-1],y);
    }
    return ;
}
void dfs(int d,int x,int y)
{
    if(d==0) return;
    int z=1;
    while(x==z||y==z) z++;
    if(x==y) 
    {
        dfs(d-1,f1[d-1],f2[d-1]);
        return ;
    }
    else
    {
        dfs_false(d-1,f1[d-1],z);
        cout<<"move"<<' '<<d<<' '<<"from"<<' '<<char(x+'A'-1)<<' '<<"to"<<' '<<char(y+'A'-1)<<endl; ans++;
        f1[d]=y;
        dfs(d-1,f1[d-1],f2[d-1]);
    }
    return ;
}
int main()
{
    int n;
    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]);
    cout<<ans;
    return 0;
}