|
|
这个,可以拿来回溯,搞个布尔型的数组判重. 倒牛奶有6种方式: C-->A C-->B B-->A B-->C A-->B A-->C 可以用bool ans[]记录答案,最后输出即可.
1 /*
2 ID:31440461
3 PROG:milk3
4 LANG:C++
5 */
6 #include<iostream>
7 using namespace std;
8 const int MAX=21;
9 struct re
10 {
11 int x,y;
12 };
13 bool state[MAX][MAX][MAX],everp=0,ans[MAX << 1];
14 int ca,cb,cc;
15
16 /*
17 前者倒牛奶给后者,c是后者的桶的容量,
18 返回tmp.x表示前者的剩余,tmp.y表示后
19 者的新牛奶量
20 */
21 re pour(int b,int e,int c)
22 {
23 re tmp;
24 if (b>c-e)
25 { tmp.x=b-c+e; tmp.y=c;}
26 else
27 { tmp.x=0; tmp.y=b+e; };
28 return tmp;
29 }
30
31
32 void handle(int a,int b,int c)
33 {
34 if (state[a][b][c]) return;
35 state[a][b][c]=1;
36 if (!a) ans[c]=1;
37 re tmp;
38 /* 下面就是倒来倒去的过程 */
39 tmp=pour(c,a,ca);handle(tmp.y,b,tmp.x); // C-->A
40 tmp=pour(c,b,cb);handle(a,tmp.y,tmp.x);// C-->B
41 tmp=pour(b,a,ca);handle(tmp.y,tmp.x,c);//B-->A
42 tmp=pour(b,c,cc);handle(a,tmp.x,tmp.y);//依次类推
43 tmp=pour(a,b,cb);handle(tmp.x,tmp.y,c);
44 tmp=pour(a,c,cc);handle(tmp.x,b,tmp.y);
45 }
46
47
48 int main()
49 {
50 freopen("milk3.in","r",stdin);
51 freopen("milk3.out","w",stdout);
52 cin >> ca >> cb >> cc;
53 handle(0,0,cc);
54 for (int i=0;i<MAX*2;i++)
55 if (ans[i])
56 {
57 if (everp) cout << ' ';
58 cout << i;
59 everp=1;
60 }
61 cout << endl;
62 return 0;
63 }
64
|