1.4.4 Mother's Mil 母亲的牛奶
Time Limit: 1 Sec Memory Limit: 64 MB
Description
农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数，最初，A和B桶都是空的，而C桶是装满牛奶的。有时，约翰把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。 写一个程序去帮助约翰找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。
Input
单独的一行包括三个整数A,B和C。
Output
只有一行，列出当A桶是空的时候，C桶牛奶所剩量的所有可能性。
Sample Input
8 9 10
Sample Output
1 2 8 9 10
思路：这个题应该用dfs，刚开始看到题，以为只需要分情况讨论一下，然后写了八个if，else然后wrong了好几发，后来才知道要用dfs进行搜索。
倒牛奶，无外乎就六种倒法，a->b , a->c , b->a , b->c , c->a , c->b ,只需要对这六种情况不断搜索就可以了，结束条件就是如果这种情况搜过了，就不需要再搜了，就return，然后有满足条件的就记录下来。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
set<int> s;
int vis[22][22][22]={0};
int A,B,C;
void dfs(int a,int b,int c)
{if(vis[a][b][c])return;vis[a][b][c]=1;if(a==0)s.insert(c);if(c>A-a)dfs(A,b,c-(A-a));elsedfs(a+c,b,0);if(c>B-b)dfs(a,B,c-(B-b));elsedfs(a,b+c,0);if(b>A-a)dfs(A,b-(A-a),c);elsedfs(a+b,0,c);if(b>C-c)dfs(a,b-(C-c),C);elsedfs(a,0,c+b);if(a>C-c)dfs(a-(C-c),b,C);elsedfs(0,b,a+c);if(a>B-b)dfs(a-(B-b),B,c);elsedfs(0,b+a,c);return ;
}
int main()
{cin>>A>>B>>C;dfs(0,0,C);int i=0;set<int>::iterator it;for(it=s.begin();it!=s.end();it++){if(!i)cout<<*it;elsecout<<" "<<*it;i++;}cout<<endl;
}