题解 P1242 【新汉诺塔】

· · 题解

这里我给大家带来一个完全正确且经过证明的方法，最后ac时间为3ms左右，还有很多值得优化的地方。

我们一起来思考一下怎么移

首先肯定是先把大盘子移到位，否则小盘子还是要动的，假设现在最大的盘子n要从A移动到B，有两种移法可能是最简便的

1、比n小的都依次移到C上，再把n移到B

2、或者把n小的都依次移到B上，再把n移到C，然后把那一堆小的移到A，把n移到B

绝大多数情况下都是第一种方案更优

为什么说绝大多数呢？因为第一种方案最后一个点是过不去的，最后一个点第二种方案更优。

然鹅特别的，有一种特殊情况，当需要移动的那一堆都在一个柱子上时，1方案一定最优，也就是说除了第一步外其他几步都是1方案最优

所以只需第一步进行一次2方案，剩下都用1方案，再进行比较就行了，不会超时，只是原方法的三倍时长

下面来证明一下这个特殊情况

最后给出代码

由于我写的很多地方都是重复的，所以代码比较长，而且很多地方可以优化

#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#define Endl endl
using namespace std;
int present[46], present1[46], present2[46];  //现在圆盘的状态即所在的柱子位置
int dest[46];  //目标状态
int n;
int Count,Count1,Count2;
void swap(int i, int pos1, int pos2)  //圆盘编号i，在第pos1的柱子上，要移到pos2的柱子上
{
    if (i == 1)  //只剩下最小的1号盘子
    {
        present[i] = pos2;
        cout << "move 1 from " << char('A' + pos1 - 1) << " to " << char('A' + pos2 - 1) << endl;
        Count++;
        return;
    }
    for (int j = i - 1; j >= 1; j--)   //把剩下的盘子都放到这两个柱子之外的那个柱子
    {
        if (present[j] != 6 - pos1 - pos2)
        {
            swap(j, present[j], 6 - pos1 - pos2);
        }
    }
    present[i] = pos2;  //移动这个大盘子
    cout << "move " << i << " from " << char('A' + pos1 - 1) << " to " << char('A' + pos2 - 1) << endl;
    Count++;
}
void swap_count1(int i, int pos1, int pos2)  //圆盘编号i，在第pos1的柱子上，要移到pos2的柱子上
{
    if (i == 1)  //只剩下最小的1号盘子
    {
        present1[i] = pos2;
        //cout << "move 1 from " << char('A' + pos1 - 1) << " to " << char('A' + pos2 - 1) << endl;
        Count1++;
        return;
    }
    for (int j = i - 1; j >= 1; j--)   //把剩下的盘子都放到这两个柱子之外的那个柱子
    {
        if (present1[j] != 6 - pos1 - pos2)
        {
            swap_count1(j, present1[j], 6 - pos1 - pos2);
        }
    }
    present1[i] = pos2;  //移动这个大盘子
    //cout << "move " << i << " from " << char('A' + pos1 - 1) << " to " << char('A' + pos2 - 1) << endl;
    Count1++;
}
void swap_count2(int i, int pos1, int pos2)  //圆盘编号i，在第pos1的柱子上，要移到pos2的柱子上
{
    if (i == 1)  //只剩下最小的1号盘子
    {
        present2[i] = pos2;
        //cout << "move 1 from " << char('A' + pos1 - 1) << " to " << char('A' + pos2 - 1) << endl;
        Count2++;
        return;
    }
    for (int j = i - 1; j >= 1; j--)   //把剩下的盘子都放到这两个柱子之外的那个柱子
    {
        if (present2[j] != 6 - pos1 - pos2)
        {
            swap_count2(j, present2[j], 6 - pos1 - pos2);
        }
    }
    present2[i] = pos2;  //移动这个大盘子
    //cout << "move " << i << " from " << char('A' + pos1 - 1) << " to " << char('A' + pos2 - 1) << endl;
    Count2++;
}
int main()  
//首先肯定是先移大盘子，假设n要从A移动到B，有两种移法
//1、比n依次小的都移到C上，再把n移到B
//2、或者把n依次小的都移到B上，再把n移到C，然后把那一堆移到A，把n移到B
//绝大多数情况下都是第一种方案更优
//特别的，当需要移动的那一堆都在一个柱子上时，1方案一定最优
//所以只需第一步进行一次2方案，剩下都用1方案，再进行比较就行了，不会超时
{
    cin >> n;
    int t2;  //圆盘编号
    int t1;  //柱上圆盘数
    for (int j = 1; j <= 3; j++)  //初始化圆盘的开始位置
    {
        cin >> t1;
        for (int i = 0; i < t1; i++)
        {
            cin >> t2;
            present[t2] = j;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        present1[i] = present2[i] = present[i];
    }
    for (int j = 1; j <= 3; j++)  //初始化圆盘的目标位置
    {
        cin >> t1;
        for (int i = 0; i < t1; i++)
        {
            cin >> t2;
            dest[t2] = j;
        }
    }
    for (int i = n; i >= 1; i--)  //一方案
    {
        if (present1[i] != dest[i])
        {
            swap_count1(i, present1[i], dest[i]);
        }
    }
    for (int i = n; i >= 1; i--)  //二方案初始化
    {
        if (present2[i] != dest[i])
        {
            swap_count2(i, present2[i], 6 - present2[i] - dest[i]);
            break;
        }
    }
    for (int i = n; i >= 1; i--)  //二方案
    {
        if (present2[i] != dest[i])
        {
            swap_count2(i, present2[i], dest[i]);
        }
    }
    if (Count1 <= Count2)
    {
        for (int i = n; i >= 1; i--)  //一方案
        {
            if (present[i] != dest[i])
            {
                swap(i, present[i], dest[i]);
            }
        }
    }
    else
    {
        for (int i = n; i >= 1; i--)  //二方案初始化
        {
            if (present[i] != dest[i])
            {
                swap(i, present[i], 6 - present[i] - dest[i]);
                break;
            }
        }
        for (int i = n; i >= 1; i--)  //二方案
        {
            if (present[i] != dest[i])
            {
                swap(i, present[i], dest[i]);
            }
        }
    }
    cout << Count << Endl;
    return 0;
}