P1215 母亲的牛奶 Mother‘s Milk【洛谷算法习题】
P1215 母亲的牛奶 Mother’s Milk
网页链接
P1215 母亲的牛奶 Mother’s Milk
题目描述
农民约翰有三个容量分别是a , b , c a,b,ca,b,c升的桶。
最初，a , b a,ba,b桶都是空的，而c cc桶是装满牛奶的。有时，农民把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。
当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。
写一个程序去帮助农民找出当a aa桶是空的时候，c cc桶中牛奶所剩量的所有可能性。
输入格式
单独的一行包括三个整数a , b , c a,b,ca,b,c。
输出格式
只有一行，升序地列出当a aa桶是空的时候，c cc桶牛奶所剩量的所有可能性。
输入输出样例 #1
输入 #1
8 9 10输出 #1
1 2 8 9 10输入输出样例 #2
输入 #2
2 5 10输出 #2
5 6 7 8 9 10说明/提示
【数据范围】
对于100 % 100\%100%的数据，1 ≤ a , b , c ≤ 20 1\le a,b,c \le 201≤a,b,c≤20。
题目翻译来自NOCOW。
USACO Training Section 1.4
解题思路
本题核心是深度优先搜索(DFS) + 状态去重，遍历所有合法的牛奶倾倒状态，求解目标答案。三个桶的牛奶总量恒定为初始值C CC，用三元组( a , b , c ) (a,b,c)(a,b,c)表示当前状态，通过三维数组标记已访问状态，避免重复搜索。枚举6种倾倒方式（A→B、A→C、B→A、B→C、C→A、C→B），每次倾倒遵循规则：将牛奶倒至目标桶满或源桶空。搜索过程中，若A AA桶为空，则记录此时C CC桶的牛奶量。最后将所有合法结果升序输出。由于数据范围极小（≤ 20 ≤20≤20），DFS 暴力搜索简洁高效，完全满足题目要求。
总结
核心逻辑：通过DFS枚举所有牛奶倾倒的合法状态，筛选出A桶为空时C桶的所有可能容量。
关键操作：三维状态标记去重、6种倾倒逻辑实现、结果收集与排序。
效率保障：极小的数据范围让暴力搜索成为最优解，代码简洁且无超时风险。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll A,B,C;ll v[22][22][22];ll r[22];voiddfs(ll a,ll b,ll c){if(v[a][b][c]==1)return;v[a][b][c]=1;if(a==0&&r[c]==0)r[c]=1;if(c>=(A-a))dfs(A,b,c-(A-a));elsedfs(c+a,b,0);if(c>=(B-b))dfs(a,B,c-(B-b));elsedfs(a,c+b,0);if(b>=(A-a))dfs(A,b-(A-a),c);elsedfs(b+a,0,c);if(b>=(C-c))dfs(a,b-(C-c),C);elsedfs(a,0,b+c);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,a+b,c);}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>A>>B>>C;dfs(0,0,C);for(ll i=0;i<=21;i++)if(r[i])cout<<i<<' ';cout<<'\n';return0;}