具体思路
设 \(f_{i,x}\) 表示 \(i\) 个盘子从 \(x\) 柱子出发的步数。
设 \(g_{i,x}\) 表示 \(i\) 个盘子从 \(x\) 柱子出发到哪个柱子。
记 \(y=g_{i-1,x}\)，\(z=6-x-y\)。
其中，\(y\) 代表将前 \(i-1\) 个盘子从 \(x\) 柱子移到的柱子，\(z\) 代表剩下的那个柱子。
分类讨论。
- 若 \(g_{i-1,y}=z\)，表示 \(i-1\) 个盘子先从 \(x\) 移到 \(y\)，第 \(i\) 个盘子从 \(x\) 移到 \(z\)，\(i-1\) 个盘子再从 \(y\) 移回 \(z\)。
\(f_{i,x}=f_{i-1,x}+1+f_{i-1,y},g_{i,x}=z\)。
- 若 \(g_{i-1,y}=x\)，表示 \(i-1\) 个盘子先从 \(x\) 移到 \(y\)，第 \(i\) 个盘子从 \(x\) 移到 \(z\)，\(i-1\) 个盘子再从 \(y\) 移回 \(x\)，第 \(i\) 个盘子从 \(z\) 移到 \(y\)，\(i-1\) 个盘子再从 \(x\) 移回 \(y\)。
\(f_{i,x}=f_{i-1,x}+1+f_{i-1,y}+1+f_{i-1,x},g_{i,x}=y\)。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=31,M=4;
int g[N][M],vis[M];LL f[N][M];
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=6;i++){
char op[10];scanf("%s",op+1);
int x=op[1]-'A'+1,y=op[2]-'A'+1;
if(vis[x])continue;
vis[x]=1;
f[1][x]=1,g[1][x]=y;
}
for(int i=2;i<=n;i++){
for(int x=1;x<=3;x++){
int y=g[i-1][x],z=6-x-y;
if(g[i-1][y]==z){
f[i][x]=f[i-1][x]+1+f[i-1][y];
g[i][x]=z;
}
if(g[i-1][y]==x){
f[i][x]=f[i-1][x]+1+f[i-1][y]+1+f[i-1][x];
g[i][x]=y;
}
}
}
printf("%lld\n",f[n][1]);
return 0;
}