原题链接：1355. 母亲的牛奶 - AcWing题库
题目：
农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。
最开始桶 A和桶 B都是空的，而桶 C里装满了牛奶。
有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。
这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。
请你编写一个程序判断，当 A桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
输入格式
共一行，包含三个整数 A,B,C。
输出格式
共一行，包含若干个整数，表示 C桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
数据范围
1≤A,B,C≤20
输入样例1：
代码语言：javascript复制8 9 10输出样例1：
代码语言：javascript复制1 2 8 9 10输入样例2：
代码语言：javascript复制2 5 10输出样例2：
代码语言：javascript复制5 6 7 8 9 10难度：中等 |
|---|
时/空限制：1s / 64MB |
总通过数：2387 |
总尝试数：3215 |
来源： usaco training 1.5 |
算法标签 BFS DFS |
解题思路：
此题主要是利用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版：
代码语言：javascript复制#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版：
代码语言：javascript复制#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。记住板子，把自己想得思路往上写即可。此题最难的地方就是一个状态的六种转移方式。只要弄明白了六种转移方式，此题就迎刃而解了。文章尚有不足，若有错误地地方请大家指出，一起进步。
