题解 P1242 【新汉诺塔】

· · 题解

这道题是建立在P4285 [SHOI2008]汉诺塔 之上的，如果没有做过，建议尝试一下。

这道题是建立在原版之上的，策略一样，也是要将盘子由初始柱经过中转柱转移至目标柱。

那么，这道题的升级在于它规定了初始与目标，还有就是---

它的各个柱子上可能都有盘子，而没有一个空柱子供你中转，这个问题等下会提到。

另外强调一下：当有大盘子要过时，小盘子统统得

滚开

这也就是上面呢个问题的难之所在，只有等大的过了，小的才能上。所以只要确定中转柱，问题便迎刃而解了。

呢么怎么确定中转柱呢？？

暴力枚举？？？？

O(∩_∩)O~ 呵呵，泽斯不可能的。

那怎么办？

=====================推理开始=======================

我们设first[x]是初始柱，last是目标柱

那么我将此时的初始柱标号以下的柱子统统转移到 6-(first[x]+y)的地方去

为什么呢？？

仔细想想：6代表的是3根初始柱，3根目标柱

6-(first[x]+y) 便是我们的中转柱了，因为到这个位置是最优的。

你应该猜到了，这个操作就是把小盘子统统移开

接下来只要安心的输出，累加计数器就可以了。 皆大欢喜

=====================推理结束=======================

泽是鄙人的代码：

#include<cstdio>
int n,last[55],first[55],ans=0,m,x;
const char ch[]={'0','A','B','C'};
//char数组的第一位要有零占位，调了n久呀，一定要吸取教训。
void dfs(int x,int y)
{
    if(first[x]==y) return;
    for(int i=x-1;i>=1;i--) dfs(i,6-(first[x]+y));
    //处理小盘子。
    printf("move %d from %c to %c\n",x,ch[first[x]],ch[y]);
    //输出。
    first[x]=y;ans++;
    //类似于并查集，找完就将x,y合并，并且累加答案数。
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=3;i++)
    {
        scanf("%d",&m);
        for(int j=1;j<=m;j++) scanf("%d",&x),first[x]=i;
    }
    for(int i=1;i<=3;i++)
    {
        scanf("%d",&m);
        for(int j=1;j<=m;j++) scanf("%d",&x),last[x]=i;
    }
    //将每一个目标与初始柱打上标记
    for(int i=n;i>=1;i--) dfs(i,last[i]);
    //第i个要到目标柱那里去。
    printf("%d",ans);
    return 0;
}

本题题解到此结束，谢谢大家。