题解 P1242 【新汉诺塔】

· · 题解

有一句话说的好：“把大象装进冰箱，永远只要3步。”

对于汉诺塔（举个例子），想要将编号为5盘从A移到C，显然编号小于5的盘既不能在C也不能在A（不能挡路），所以它们必须在B上。

有以上一点可知道：要将K从X移动到Y上，其最少次数的操作中必须有一部分操作是为了必须将编号小于K的盘子移动到Z上

那么我们要将编号小于K的盘子从X移到Y上（经典汉诺塔），有以下几个操作：

1.将编号小于K的盘子全部移动到Z上

2.将K移动到Y上

3.将编号小于K的盘子移动到Y上

不过这道题改了一下……

很显然的是，对于给定的盘K，如果K已经在它自己的位子上了，那么不要动他（如果能）显然是最优的，而且它不会影响到编号小于K的任何操作

那么，我们用数组now[K]记录盘子K当前所处的柱子（1，2，3），用数组dest[k]记录盘子K的目标柱子（最终目标）

然后按编号从大到小枚举K，如果now[K] = dest[K],显然它就不要动了，大家当他不存在就好

可是如果我们碰到了需要编号的K盘怎么办

那么我们应该先将编号小于K的盘子移动到第三根柱子上，再将K移过去，于是编号小于K的盘子就留在第三根柱子上，而K完成了它的目标，就可以认为K不存在，继续枚举K了。

于是，当K的1的时候，大家都可以看作不存在了，于是达到了目标，天下大同

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

namespace my
{
    int now[112], dest[112];
    int other[4][4];
    int n;

    void init()
    {
        other[1][2] = 3;
        other[2][1] = 3;
        other[1][3] = 2;
        other[3][1] = 2;
        other[2][3] = 1;
        other[3][2] = 1;
    }

    void read(int *dest)
    {
        for (int i(1); i <= 3; ++i)
        {
            int k;
            scanf("%d", &k);
            for (int j(0); j != k; ++j)
            {
                int in;
                scanf("%d", &in);
                dest[in] = i;
            }
        }
    }


    int cnt;

    void OldHnoi(int rank, int to)//将编号小于K的盘全部移动到柱子to上
    {
        if (rank <= 0) return;
        if (now[rank] == to)
        {    
            OldHnoi(rank - 1, to);
            return;
        }
        OldHnoi(rank - 1, other[now[rank]][to]);
        printf("move %d from %c to %c\n", rank, 'A' + now[rank] - 1, 'A' + to - 1);
        now[rank] = to;
        ++cnt;
        OldHnoi(rank - 1, to);
    }

    //将编号为rank的盘移动到to上，而编号小于rank的盘子会被移动到other[now[rank]][to]上
    void move(int rank, int to)
    {
        if (rank <= 0) return;
        if (now[rank] == to)
        {    
            OldHnoi(rank - 1, to);
            return;
        }
        OldHnoi(rank - 1, other[now[rank]][to]);
        printf("move %d from %c to %c\n", rank, 'A' + now[rank] - 1, 'A' + to - 1);
        now[rank] = to;
        ++cnt;
    }
}

int main()
{
    my::init();
    scanf("%d", &my::n);
    my::read(my::now);
    my::read(my::dest);
    for (int i(my::n); i != 0; --i)
    {
        if (my::now[i] != my::dest[i])
        {
            my::move(i, my::dest[i]);
        }
    }
    printf("%d\n", my::cnt);
    return 0;
}