|
这个,可以拿来回溯,搞个布尔型的数组判重. 倒牛奶有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);//依次类推![](http://www.cppblog.com/Images/dot.gif) 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
|