题目： 农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数，
最初，A和B桶都是空的，而C桶是装满牛奶的。有时，约翰把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。
写一个程序去帮助约翰找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。
递归的题除了书上有代码的几乎没打....（虽然那代码还一堆Bug...）
这道题点开了快十回就是没思路。主要是想边界条件和倒得策略。
其实觉得和拍卖的题差不多，主要思路是DFS搜索。打了好久然后bug了，内心有点崩
1 void dfs(int x,int y,int z) 2 { 3 if(x==0) ans[z]=1; 4 if((fa[x]==1)&&(fb[y]==1)&&(fc[z]==1)) return; 5 fa[x]=1;fb[y]=1;fc[z]=1; 6 //x is 0 ,milk 7 int tx,ty,tz; 8 if(y!=0)//y not empty 9 { 10 tx=x;ty=y;tz=z; 11 tx+=ty;ty=0;// y>>x 12 if(tx>a) {ty+=tx-a;tx=a;} 13 dfs(tx,ty,tz); 14 15 tx=x;ty=y;tz=z;// y>>z 16 tz+=ty;ty=0; 17 if(tz>c) {ty+=tz-c;tz=c;} 18 dfs(tx,ty,tz); 19 } 20 21 if(z!=0)//z not empty 22 { 23 tx=x;ty=y;tz=z;//z>>x 24 tx+=tz;tz=0; 25 if(tx>a){tz+=tx-a;tx=a;} 26 dfs(tx,ty,tz); 27 28 tx=x;ty=y;tz=z;//z>>y 29 ty+=tz;tz=0; 30 if(ty>b){tz+=ty-b;ty=b;} 31 dfs(tx,ty,tz); 32 } 33 34 35 if(x!=0) 36 { 37 tx=x;ty=y;tz=z; 38 ty+=tx;tx=0; 39 if(ty>b){tx+=ty-b;ty=b;} 40 dfs(tx,ty,tz); 41 42 tx=x;ty=y;tz=z; 43 tz+=tx;tx=0; 44 if(tz>c){tx+=tz-c;tz=c;} 45 dfs(tx,ty,tz); 46 } 47 }
这是主要策略代码。无非是6个递归，从a倒b，a倒c，b倒a，b倒c……
关于边界条件本来我是开了一个bool判断c的情况，出现过就return。但是c出现过，a和b的情况还有很多种。于是开了三个bool数组模拟出现的情况。
小细节问题：刚开始我把ans赋值数组放在了return后面，那么就会漏情况...因为如果策略唯一还没赋值就要return。
主函数dfs刚开始我写的dfs（a，b，c）....纠结10分钟才发现。细节决定成败..别忘了只有c有牛奶orz