由每个最末的状态(n,n,n)推得所有可行的状态,并记录被推得状态的来源和步长,类似筛法的方式,没有被扩展到的情况即无法到达的情况,标记其步长仍为0.
1
#include<stdio.h>
2
#include<string.h>
3
4
struct Q
{
5
int flag;
6
int a;
7
int b;
8
int c;
9
};
10
Q f[61][61][61];
11
12
int chang1(Q t);
13
int chang2(Q t);
14
int chang3(Q t);
15
int chang4(Q t);
16
int chang5(Q t);
17
int chang6(Q t);
18
19
int chang1(Q t)
{
20
Q ne;
21
if(t.a%2 !=0 ) return 0 ;
22
ne.a = t.a /2;
23
ne.b = t.b+ne.a;
24
ne.c = t.c;
25
26
if(ne.a == ne.b && ne.b == ne.c) return 0 ;
27
if(f[ne.a][ne.b][ne.c].flag != 0 && f[ne.a][ne.b][ne.c].flag<t.flag+1) return 0 ;
28
f[ne.a][ne.b][ne.c].flag = t.flag+1;
29
f[ne.a][ne.b][ne.c].a=t.a;
30
f[ne.a][ne.b][ne.c].b=t.b;
31
f[ne.a][ne.b][ne.c].c=t.c; ne.flag = t.flag+1;
32
return chang1(ne)+chang2(ne)+chang3(ne)+chang4(ne)+chang5(ne)+chang6(ne);
33
}
34
int chang2(Q t)
{
35
Q ne;
36
if(t.a%2 !=0 ) return 0 ;
37
ne.a = t.a /2;
38
ne.c = t.c+ne.a;
39
ne.b = t.b;
40
41
if(ne.a == ne.b && ne.b == ne.c) return 0 ;
42
if(f[ne.a][ne.b][ne.c].flag != 0 && f[ne.a][ne.b][ne.c].flag<t.flag+1) return 0 ;
43
f[ne.a][ne.b][ne.c].flag = t.flag+1;
44
f[ne.a][ne.b][ne.c].a=t.a;
45
f[ne.a][ne.b][ne.c].b=t.b;
46
f[ne.a][ne.b][ne.c].c=t.c; ne.flag = t.flag+1;
47
return chang1(ne)+chang2(ne)+chang3(ne)+chang4(ne)+chang5(ne)+chang6(ne);
48
}
49
int chang3(Q t)
{
50
Q ne;
51
if(t.b%2 !=0 ) return 0 ;
52
ne.b = t.b /2;
53
ne.a = t.a+ne.b;
54
ne.c = t.c;
55
56
if(ne.a == ne.b && ne.b == ne.c) return 0 ;
57
if(f[ne.a][ne.b][ne.c].flag != 0 && f[ne.a][ne.b][ne.c].flag<t.flag+1) return 0 ;
58
f[ne.a][ne.b][ne.c].flag = t.flag+1;
59
f[ne.a][ne.b][ne.c].a=t.a;
60
f[ne.a][ne.b][ne.c].b=t.b;
61
f[ne.a][ne.b][ne.c].c=t.c; ne.flag = t.flag+1;
62
return chang1(ne)+chang2(ne)+chang3(ne)+chang4(ne)+chang5(ne)+chang6(ne);
63
}
64
int chang4(Q t)
{
65
Q ne;
66
if(t.b%2 !=0 ) return 0 ;
67
ne.b = t.b /2;
68
ne.c = t.c+ne.b;
69
ne.a = t.a;
70
71
if(ne.a == ne.b && ne.b == ne.c) return 0 ;
72
if(f[ne.a][ne.b][ne.c].flag != 0 && f[ne.a][ne.b][ne.c].flag<t.flag+1) return 0 ;
73
f[ne.a][ne.b][ne.c].flag = t.flag+1;
74
f[ne.a][ne.b][ne.c].a=t.a;
75
f[ne.a][ne.b][ne.c].b=t.b;
76
f[ne.a][ne.b][ne.c].c=t.c; ne.flag = t.flag+1;
77
return chang1(ne)+chang2(ne)+chang3(ne)+chang4(ne)+chang5(ne)+chang6(ne);
78
}
79
80
int chang5(Q t)
{
81
Q ne;
82
if(t.c%2 !=0 ) return 0 ;
83
ne.c = t.c /2;
84
ne.a = t.a+ne.c;
85
ne.b = t.b;
86
87
if(ne.a == ne.b && ne.b == ne.c) return 0 ;
88
if(f[ne.a][ne.b][ne.c].flag != 0 && f[ne.a][ne.b][ne.c].flag<t.flag+1) return 0 ;
89
f[ne.a][ne.b][ne.c].flag = t.flag+1;
90
f[ne.a][ne.b][ne.c].a=t.a;
91
f[ne.a][ne.b][ne.c].b=t.b;
92
f[ne.a][ne.b][ne.c].c=t.c; ne.flag = t.flag+1;
93
return chang1(ne)+chang2(ne)+chang3(ne)+chang4(ne)+chang5(ne)+chang6(ne);
94
}
95
int chang6(Q t)
{
96
Q ne;
97
if(t.c%2 !=0 ) return 0 ;
98
ne.c = t.c /2;
99
ne.b = t.b+ne.c;
100
ne.a = t.a;
101
102
if(ne.a == ne.b && ne.b == ne.c) return 0 ;
103
if(f[ne.a][ne.b][ne.c].flag != 0 && f[ne.a][ne.b][ne.c].flag<t.flag+1) return 0 ;
104
f[ne.a][ne.b][ne.c].flag = t.flag+1;
105
f[ne.a][ne.b][ne.c].a=t.a;
106
f[ne.a][ne.b][ne.c].b=t.b;
107
f[ne.a][ne.b][ne.c].c=t.c; ne.flag = t.flag+1;
108
return chang1(ne)+chang2(ne)+chang3(ne)+chang4(ne)+chang5(ne)+chang6(ne);
109
}
110
void init()
{
111
Q temp ;
112
for(int i = 1 ; i <= 20 ; i++ )
{
113
f[i][i][i].a = i;
114
f[i][i][i].b = i;
115
f[i][i][i].c = i;
116
f[i][i][i].flag = 0;
117
temp = f[i][i][i];
118
if (i % 2 != 0 )continue;
119
chang1(temp)+chang2(temp)+chang3(temp)+chang4(temp)+chang5(temp)+chang6(temp);
120
}
121
}
122
int main()
{
123
init();
124
Q f2;
125
while(scanf("%d%d%d",&f2.a,&f2.b,&f2.c)!=EOF)
{
126
printf("%4d%4d%4d\n",f2.a,f2.b,f2.c);
127
while(f[f2.a][f2.b][f2.c].flag)
{
128
printf("%4d%4d%4d\n",f[f2.a][f2.b][f2.c].a,f[f2.a][f2.b][f2.c].b,f[f2.a][f2.b][f2.c].c);
129
f2 = f[f2.a][f2.b][f2.c];
130
}
131
printf("============\n");
132
}
133
return 0 ;
134
}
135