题解 | #牛牛的汉诺塔#

思路

考察递归和记忆化搜索，记忆化搜索忘了咋写，利用同个n的递归移动次数相同的性质可将递归次数减少一半；移动情况以及次数信息由map维护

#include <bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0)
#define ll long long
#define endl '\n'
using namespace std;

map<pair<char,char>,ll> mp;
void Init_map(){
    char c = 'A';
    for(int i = 0;i <= 2;i++)
        for(int j = 0;j <= 2;j++)
            if(i == j) continue;
            else mp[make_pair(c+i,c+j)] = 0;
}
void disp_map(){
    char c = 'A';
    ll sum = 0;
    for(int i = 0;i <= 2;i++)
        for(int j = 0;j <= 2;j++)
            if(i == j) continue;
            else{
                cout<<char(c+i)<<"->"<<char(c+j)<<":";
                cout<<mp[make_pair(c+i,c+j)]<<endl;
                sum += mp[make_pair(c+i,c+j)];
            }
    cout<<"SUM:"<<sum;
}

void Hanoi(int n,char a,char b,char c){    //意为将n个盘从a柱移到c柱，b为中转柱
    if(n == 1) mp[make_pair(a,c)]++;
    else{
        Hanoi(n-1,a,c,b);
        //Hanoi(n-1,b,a,c);
        ll tmp1 = mp[make_pair(c,a)],tmp2 = mp[make_pair(c,b)],
        tmp3 = mp[make_pair(a,c)],tmp4 = mp[make_pair(a,b)],
        tmp5 = mp[make_pair(b,c)],tmp6 = mp[make_pair(b,a)];
        mp[make_pair(a,b)] += tmp1;
        mp[make_pair(a,c)] += tmp2;
        mp[make_pair(b,a)] += tmp3;
        mp[make_pair(b,c)] += tmp4;
        mp[make_pair(c,a)] += tmp5;
        mp[make_pair(c,b)] += tmp6;
        //两次n-1递归中移动次数相等，只需算一次递归即可
        mp[make_pair(a,c)]++;
    }
}

int main(){
    ios;
    int n;
    cin>>n;
    Init_map();    //初始化每种移动情况数
    Hanoi(n,'A','B','C');
    disp_map();    //打印结果
    return 0;
}