这是大白书上的例题，刘汝佳的解题方法很巧妙。要把初始盘子移到最终状态，先把最大的盘子安置好，否则无法成功，所以先找到最大的没在最终柱的盘子，先移到该盘子所在柱子上只有该盘子，并且其他盘子都在中转柱上（已经进入最终柱的最大盘子不考虑了），通过一个递归解得到该状态的步数，然后放完该盘子之后，就变成了一个柱子上放剩余盘子，由底向上把剩余的盘子按终态放好，需要用到汉诺塔的一个已知结论就是把一个汉诺塔的所有盘子从一个柱子移到另一个柱子上，需要用2的n次方-1步。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <iostream>#include <cstdio>#include <cstring>#define ll long longusing
namespace std;
int n,start[100],fina[100];
ll f(int* p,int
i,int
finall)
{ if
(i==0) return
0;
if
(p[i]==finall) return
f(p,i-1,finall);
ll temp=1;
return
f(p,i-1,6-p[i]-finall)+(temp<<(i-1));
}int
main()
{ int
t=0;
while
(scanf("%d",&n))
{
if
(!n) break;
for
(int
i=1;i<=n;i++)
{
scanf("%d",&start[i]);
}
for
(int
j=1;j<=n;j++)
{
scanf("%d",&fina[j]);
}
int
k=n;
while
(k>=1 && start[k]==fina[k]) k--;
ll ans=0;
if
(k>=1)
{
int
other =6-start[k]-fina[k];
ans=f(start,k-1,other)+f(fina,k-1,other)+1;
}
printf("Case %d: %lld\n",++t,ans);
}
return
0;
} |