农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数， 最初，A和B桶都是空的，而C桶是装满牛奶的。有时，农民把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。
写一个程序去帮助农民找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。
输入格式：
单独的一行包括三个整数A,B和C。
输出格式：
只有一行，升序地列出当A桶是空的时候，C桶牛奶所剩量的所有可能性。
输入样例#1：
[输入1] 8 9 10 [输入2] 2 5 10输出样例#1：
[输出1] 1 2 8 9 10 [输出2] 5 6 7 8 9 10暴力搜索，
AC代码：
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int ta,tb,tc,k,ans[1020],vis[22][22][22]; //nowa为当前a杯子的奶的多少，ta为a杯子的容量。 void dfs(int nowa,int nowb,int nowc) { if(vis[nowa][nowb][nowc]) return; if(nowa==0) ans[++k]=nowc; vis[nowa][nowb][nowc]=1; if(nowc) { if(nowa<ta) dfs(min(ta,nowa+nowc),nowb,nowc-(min(ta,nowa+nowc)-nowa)); if(nowb<tb) dfs(nowa,min(nowb+nowc,tb),nowc-(min(tb,nowb+nowc)-nowb)); } if(nowb) { if(nowa<ta) dfs(min(ta,nowa+nowb),nowb-(min(ta,nowa+nowb)-nowa),nowc); if(nowc<tc) dfs(nowa,nowb-(min(tc,nowc+nowb)-nowc),min(tc,nowc+nowb)); } if(nowa) { if(nowb<tb) dfs(nowa-(min(tb,nowa+nowb)-nowb),min(tb,nowa+nowb),nowc); if(nowc<tc) dfs(nowa-(min(tc,nowa+nowc)-nowc),nowb,min(tc,nowc+nowa)); } return; } int main(){ scanf("%d%d%d",&ta,&tb,&tc); dfs(0,0,tc); sort(ans+1,ans+k+1); for(int i=1;i<=k;i++) printf("%d ",ans[i]); return 0; }
