题目：
农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。
最开始桶 A和桶 B都是空的，而桶 C里装满了牛奶。
有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。
这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。
请你编写一个程序判断，当 A桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
输入格式
共一行，包含三个整数 A,B,C。
输出格式
共一行，包含若干个整数，表示 C桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
数据范围
1≤A,B,C≤20
输入样例1：
8 9 10
输出样例1：
1 2 8 9 10
输入样例2：
2 5 10
5 6 7 8 9 10
| 难度：中等 |
| 时/空限制：1s / 64MB |
| 总通过数：2387 |
| 总尝试数：3215 |
| 来源： |
| 算法标签 |
解题思路：
此题主要是利用DFS、BFS搜索，题目数据量很小，时间复杂度为O(ABC)，DFS、BFS都可以过。一个状态（a,b,c）可以有6种方案，可以a往b倒、a往c倒、b往a倒、b往c倒、c往a倒、c往b倒，用搜索把六种状态都都搜索一遍，用vis三维数组标记是否被搜过，最后再找一下A桶为0,C桶的体积即可。
这里解释一下样例，开始我也没看懂什么意思，c->a表示C桶往A桶倒每一个状态都可以向下转移搜索，红色框表示符合题意A=0。
DFS版：
#include<iostream> using namespace std; const int N = 25; int A,B,C; bool vis[N][N][N]; void dfs(int a,int b,int c){//abc表示此时三个桶牛奶的体积 if(vis[a][b][c])return;//重复搜索 vis[a][b][c]=true; if(a>B-b)dfs(a-B+b,B,c);//a往b里面倒 else dfs(0,a+b,c); if(a>C-c)dfs(a-C+c,b,C);//a往c里面倒 else dfs(0,b,a+c); if(b>A-a)dfs(A,b-A+a,c);//b往a里面倒 else dfs(a+b,0,c); if(b>C-c)dfs(a,b-C+c,C);//b往c里面倒 else dfs(a,0,b+c); if(c>A-a)dfs(A,b,c-A+a);//c往a里面倒 else dfs(a+c,b,0); if(c>B-b)dfs(a,B,c-B+b);//c往b里面倒 else dfs(a,b+c,0); } int main(){ cin>>A>>B>>C; dfs(0,0,C); for(int i=0;i<=C;i++){//升序输出，先枚举C桶 for(int j=0;j<=B;j++){ if(vis[0][j][i]){ cout<<i<<" "; break; } } } return 0; }
BFS版：
#include<iostream> #include<queue> using namespace std; const int N=25; int A,B,C; bool vis[N][N][N]; struct node{ int a,b,c; }; queue<node> q; void insert(int a,int b,int c){ if(!vis[a][b][c]){ q.push({a,b,c}); vis[a][b][c]=true; } } void bfs(){ while(q.size()){ auto t=q.front(); q.pop(); int x=t.a,y=t.b,z=t.c;//把六种情况枚举一遍 insert(x-min(x,B-y),min(B,x+y),z);//a往b里面倒 insert(x-min(x,C-z),y,min(C,x+z));//a往c里面倒 insert(min(A,x+y),y-min(y,A-x),z);//b往a里面倒 insert(x,y-min(y,C-z),min(y+z,C));//b往c里面倒 insert(min(x+z,A),y,z-min(z,A-x));//c往a里面倒 insert(x,min(B,y+z),z-min(z,B-y));//c往b里面倒 } } int main(){ cin>>A>>B>>C; q.push({0,0,C}); vis[0][0][C]=true; bfs(); for(int i=0;i<=C;i++){ for(int j=0;j<=B;j++){ if(vis[0][j][i]){ cout<<i<<" "; break; } } } return 0; }
总结：
主要考察DFS、BFS。记住板子，把自己想得思路往上写即可。此题最难的地方就是一个状态的六种转移方式。只要弄明白了六种转移方式，此题就迎刃而解了。文章尚有不足，若有错误地地方请大家指出，一起进步。
