要说USACO里最经典的搜索入门题Mothers Milk绝对排得上号。这道题表面上是三个桶倒来倒去的模拟本质上考的是状态搜索和去重看起来简单但对刚接触算法竞赛的人来说能把状态定义想清楚、把DFS/BFS写对就已经是一次很扎实的锻炼。我自己第一次写的时候满脑子都是“怎么把牛奶倒来倒去”结果代码写得又乱又长后来才意识到核心是状态压缩和访问标记。这篇就用JAVA完整实现一遍把从题目理解到代码落地再到调试优化的全过程都展开讲适合正在刷USACO、准备蓝桥杯或者刚学搜索算法的朋友参考。1. 题目理解与核心思路拆解1.1 三桶牛奶到底在考察什么原题不复杂三个桶分别有容量A、B、C初始时A桶和B桶都是空的C桶装满牛奶。你可以反复执行“把一个桶里的牛奶倒入另一个桶”倒的规则只有一个——要么源桶倒空要么目标桶倒满。最终要找出所有可能的C桶牛奶量条件是A桶为空。第一眼看去这就是个模拟题但仔细想每倒一次三个桶的牛奶量就变成一个新的三元组整个倒奶过程会形成一个状态网络。比如(0, 0, 10)可以倒出很多种状态这些状态之间又有转移关系。所以这道题真正考察的不是“你会不会if-else模拟倒奶”而是“你能不能把状态找全并且不重复、不遗漏”。这就是为什么USACO把它放在搜索专题里。无论你用深度优先搜索还是广度优先搜索本质上都是在遍历状态空间。更妙的是这道题隐含了一个守恒条件总牛奶量始终等于C桶初始容量因为整个过程没有牛奶凭空产生或消失。利用这个条件我们可以把三维状态压缩成二维这既是优化也是理解深度的体现。1.2 状态定义与压缩的关键三个桶的当前牛奶量可以用(a, b, c)表示a是A桶奶量b是B桶奶量c是C桶奶量。初始状态是(0, 0, cMax)其中cMax是C桶容量也就是总奶量Milk cMax。如果直接用三维数组visited[a][b][c]来判重当然不会错但会有些浪费因为a、b、c三个值并不是独立变化的。每时每刻都有c Milk - a - b也就是说只要知道a和bc就被唯一确定了。所以访问标记只需要二维就够了boolean[aMax 1][bMax 1]记为visited[a][b] true表示“A桶有a单位奶、B桶有b单位奶”这个状态已经搜过。这里有个容易忽略的点c不能直接通过cMax - a - b来算因为C桶初始奶量是cMax但B桶和A桶可能也有奶所以C桶当前奶量 总奶量 - a - b cMax - a - b这个关系在代码里要一直记住。很多初学者到这里会懵习惯性地想用a、b、c三个变量都存下来其实理解了守恒条件代码会清爽很多。1.3 为什么搜索而不是贪心或者动态规划有人可能会问能不能直接推导出所有可能结果理论上可以枚举但状态之间的转移关系呈“网络状”一个状态可以由多个路径到达而且倒奶顺序会影响中间状态但不影响最终可达集合。这种“多条路径汇聚到同一状态”的结构天然适合搜索去重。动态规划也可行本质思路和搜索一致都是按状态转移但题目不要求最优解、不要求计数只要求输出所有可达结果所以搜索是最直观的。DFS和BFS都能做DFS代码短、写起来顺手BFS层次清晰适合打印路径。这道题我推荐DFS因为状态数很少递归深度只有几百层完全不会栈溢出代码也更紧凑。2. 核心细节解析与倒奶逻辑实现2.1 六种倒法如何抽象三个桶之间的倒奶一共有6种方向A到B、A到C、B到A、B到C、C到A、C到B。每一种倒法的本质都是同一个动作从源桶x向目标桶y倒奶倒出的量由两个条件共同决定源桶里有奶奶量记作cur[x]目标桶还有空余容量空余量记作cap[y] - cur[y]。实际倒出的量是这两个值中的较小值也就是pour Math.min(cur[x], cap[y] - cur[y])。如果pour等于0说明源桶空或者目标桶满此时状态不发生任何变化递归进去会立刻被visited拦截所以不会死循环但为了减少无效递归也可以选择只在pour 0时才继续搜索。这个min的逻辑是整个程序的核心写错就会闹出“牛奶越倒越多”的笑话。比如A桶有5升B桶还能装3升这时倒出的量必须是3升而不是5升否则B桶就超容量了。反过来A桶有2升B桶能装10升倒出的量就是2升因为源桶先空。我见过不少初学代码的人在这里写一个if判断分情况讨论其实完全没有必要一个Math.min就把两种情况都覆盖了。2.2 DFS搜索框架的编写要点DFS的递归函数可以定义成void dfs(int a, int b, int c)a、b、c分别代表三个桶当前奶量。每进入一个状态先检查visited[a][b]是否已经为true如果搜过就直接返回否则标记为已访问。这样能保证每个状态最多被完整展开一次避免指数级重复搜索。标记完之后如果a 0说明当前状态下A桶是空的这就是题目要求收集的时刻。此时把c的值记下来存入结果集合。这里有个细节结果的顺序必须是升序而且不能有重复值。我建议用TreeSet 来收集结果它天然有序且自动去重省去后面排序的步骤。如果题目要求的输出格式支持无序也可以用HashSet但USACO要求升序所以TreeSet最省心。接下来就是6个方向分别递归。以A到B为例代码大致是// A - B int pourAB Math.min(a, bMax - b); dfs(a - pourAB, b pourAB, c);因为c Milk - a - b所以A桶倒出pourAB后a减少、b增加c自然等于Milk - (a - pourAB) - (b pourAB)你会发现括号里互相抵消c不变。这从物理意义上也很好理解A和B之间的倒奶不会影响C桶的奶量。同理其他五个方向也都是改两个桶的值第三个桶保持不变不需要显式计算。2.3 完整JAVA代码下面给出一个可以直接运行的完整版本输入三个整数A、B、C输出所有可能的C桶奶量。为了方便本地测试代码里使用了Scanner读取标准输入如果你想提交到USACO训练系统只需要把读入和输出改成文件流即可后面我会专门说明。import java.util.Scanner; import java.util.TreeSet; public class MotherMilk { static int aMax, bMax, cMax; static int milkTotal; static boolean[][] visited; static TreeSetInteger result new TreeSet(); public static void main(String[] args) { Scanner sc new Scanner(System.in); aMax sc.nextInt(); bMax sc.nextInt(); cMax sc.nextInt(); sc.close(); milkTotal cMax; visited new boolean[aMax 1][bMax 1]; dfs(0, 0, cMax); StringBuilder sb new StringBuilder(); for (int v : result) { sb.append(v).append( ); } System.out.println(sb.toString().trim()); } static void dfs(int a, int b, int c) { if (visited[a][b]) { return; } visited[a][b] true; if (a 0) { result.add(c); } // A - B int pour Math.min(a, bMax - b); dfs(a - pour, b pour, c); // A - C pour Math.min(a, cMax - c); dfs(a - pour, b, c pour); // B - A pour Math.min(b, aMax - a); dfs(a pour, b - pour, c); // B - C pour Math.min(b, cMax - c); dfs(a, b - pour, c pour); // C - A pour Math.min(c, aMax - a); dfs(a pour, b, c - pour); // C - B pour Math.min(c, bMax - b); dfs(a, b pour, c - pour); } }这段代码的运行逻辑很直接从初始状态(0, 0, cMax)出发不断尝试6种倒奶方式每到一个新状态就标记并判断是否满足a 0。最终TreeSet里存的就是所有满足条件的C桶奶量。用样例8 9 10测试输出是1 2 8 9 10和USACO题目给的样例完全一致。这意味着状态遍历没有遗漏倒奶逻辑也没有算错。如果你用自己随手写的模拟方式去验算会发现这五个值都能通过一系列操作得到而且中间状态确实都没有违反“桶容量限制”。3. 测试验证、常见问题与调试技巧3.1 边界条件一定要自己构造用例很多人刷题时只测题目样例过了就觉得自己AC了这是竞赛里很危险的习惯。Mothers Milk这道题边界情况其实不少我列举几个值得测的最小容量输入1 1 1初始C桶有1升奶A桶为空所以答案就是1。程序输出也应该是1。A桶容量为0输入0 5 10A桶永远为空那C桶的奶量就是总奶量10吗不是因为可以把C的奶往B倒C还剩5然后C再倒5C又变回10。实际上当A恒为空时C可以是10和5取决于B有没有奶。这个用例能帮你确认visited数组的维度是否正确。最大容量输入20 20 20状态空间是21×21441个搜索完全没有压力但你可以借此验证TreeSet输出空格格式是否干净。这些边界用例一个比一个容易出错。特别是A桶容量为0的情况如果你在visited初始化时写成了new boolean[aMax][bMax]访问visited[0][0]时可能看似没事但访问visited[aMax][bMax]时就会数组越界。所以visited的每个维度都要加1对应容量0到容量最大值总共是容量1个取值。3.2 数组越界和状态漏搜的常见原因如果是数组越界问题几乎都出在visited的维度计算上。用new boolean[aMax 1][bMax 1]就不会有问题。但如果你习惯把状态定义成“a的范围是0到aMax”就会下意识写成boolean[aMax][bMax]那么当状态是(aMax, bMax)时访问visited[aMax][bMax]就越界了。这是个典型的差一错误off-by-one error排查方法很简单把所有变量的取值范围标注清楚再检查数组下标最大值是否等于容量本身。状态漏搜的原因则更多样。最常见的是只从“当前状态”往六个方向递归却漏掉了某些方向或者把某个方向写反比如B到A的动态加到了a上、减到了b上但其实应该反过来。我建议写完六个方向的递归后逐个检查源桶奶量减pour、目标桶奶量加pour其他桶不变。这个检查只要慢下来基本能一眼发现错误。还有一类问题是visited标记的位置不对。如果你把visited[a][b] true写在判断a 0之后会导致同一个状态被重复递归多次虽然结果可能还是对的但效率下降不少而且可能造成递归过深。正确的做法是进入函数后先判重、再标记、再处理业务逻辑。判重和标记必须紧挨着中间不要插入其他代码这是DFS的通用模板。3.3 输出格式为什么必须用StringBuilderUSACO这类OJ对输出格式要求很严格行末不允许有多余空格多个数字之间用一个空格分隔。如果你用System.out.print循环输出很容易在最后一个数字后面多打一个空格导致Presentation Error。用StringBuilder拼接最后trim()一下是最稳妥的写法StringBuilder sb new StringBuilder(); for (int v : result) { sb.append(v).append( ); } System.out.println(sb.toString().trim());如果结果集为空trim后的字符串为空字符串输出一个空行这符合题意吗在这道题中不会出现空集因为初始状态C桶满、A桶空至少有一个值满足条件所以你不用担心。但在其他搜索题中养成“处理空结果”的意识会更好。3.4 本地调试的实用技巧这类搜索题的调试最有效的手段是打印状态转移路径。你可以在dfs函数开头加一行临时输出System.out.println(a a , b b , c c);跑一遍小数据人工检查状态序列是否符合倒奶规则。检查完记得删掉否则提交时会输出多余内容。另外如果出现“StackOverflowError”先别急着怀疑递归深度这道题状态数很小正常搜索不会栈溢出。真溢出了大概率是visited没有正确标记导致死循环递归。检查visited数组有没有在递归前被赋值是解决这类问题的第一步。4. 从DFS到BFS的等价实现4.1 BFS的写法和适用场景DFS能解的题BFS通常也能解。这道题用BFS同样简单思路完全一致只是把递归栈换成了显式队列。我给出一个核心片段代码主体和DFS版几乎一样区别在于搜索顺序import java.util.ArrayDeque; import java.util.Queue; static void bfs() { Queueint[] queue new ArrayDeque(); queue.offer(new int[]{0, 0, cMax}); visited[0][0] true; while (!queue.isEmpty()) { int[] cur queue.poll(); int a cur[0], b cur[1], c cur[2]; if (a 0) { result.add(c); } // A - B int pour Math.min(a, bMax - b); int na a - pour, nb b pour, nc c; if (!visited[na][nb]) { visited[na][nb] true; queue.offer(new int[]{na, nb, nc}); } // 其余五个方向同理略... } }BFS和DFS在当前题目上没有本质区别因为我们要遍历所有状态而不是找最短路径。但如果题目变成“求最少倒奶次数”BFS就更有优势因为它天然按照层数扩展第一次访问到目标状态时的层数就是最优解。所以我建议你两个版本都写一遍既加深对状态转移的理解也为以后解决路径类问题打基础。4.2 为什么DFS在本题更“省代码”从代码量来看DFS明显更短。BFS需要显式维护队列每个方向都要进行visited判断和入队操作代码行数会多不少。DFS则只需要递归调用判断逻辑统一放在函数开头结构干净。这其实反映出两种搜索适用于不同思维习惯的场景DFS适合“先闯到底再回头”的思维BFS适合“一层层推进按部就班”的思维。我个人的习惯是状态空间小、不要求最短路径、不需要打印路径时首选DFS状态空间大、担心递归栈溢出或需要最短步数时选BFS。Mothers Milk的441个状态用哪种都无所谓但DFS的简洁性会更舒服。5. 进阶优化与这类题的共通道理5.1 状态编码从二维数组到位运算如果这道题的容量变大比如A、B、C都扩充到1000二维boolean数组可能就太大了。这时可以把状态压缩成一个整数用state a * (bMax 1) b作为唯一编码再用HashSet 或者boolean数组去存储访问状态。这样可以把二维状态空间映射到一维在内存上更加紧凑逻辑上也更接近“状态压缩”的思想。int encode(int a, int b) { return a * (bMax 1) b; }需要取回a和b时用除法和取模a state / (bMax 1)b state % (bMax 1)。这种做法在更复杂的搜索题里很常见尤其是涉及地图、棋盘、多物体移动的题目比如八数码问题就经常用康托展开或者二进制位压缩来表示状态。Mothers Milk虽然用不上这种优化但通过它去理解状态编码的思路对后续刷题非常有帮助。5.2 面向对象封装倒奶操作如果想把代码写得更有复用性可以把“倒奶”抽象成一个方法传入三个桶的当前奶量以及来源桶和目标桶编号方法内部计算转移量并返回新状态。这样做的好处是代码的可读性更高六个方向不再是六段重复的代码而是一个循环配一个二维数组来枚举方向。static int[] pour(int[] cur, int src, int dst, int[] cap) { int[] res cur.clone(); int move Math.min(cur[src], cap[dst] - cur[dst]); res[src] - move; res[dst] move; return res; }然后主循环里枚举源桶和目标桶for (int src 0; src 3; src) { for (int dst 0; dst 3; dst) { if (src dst) continue; int[] next pour(new int[]{a, b, c}, src, dst, capArray); dfs(next[0], next[1], next[2]); } }这种写法更接近“状态转移”的抽象层面对于状态数组长度不固定或者状态维度更多的题目它的扩展性优势就显现出来了。我建议你在掌握裸DFS写法之后尝试改写一版面向对象的实现这能帮你形成“状态转移”的通用思维模型。5.3 从一题到一类搜索题的通用模板Mothers Milk几乎涵盖了搜索题的所有核心要素明确的状态定义、有限的转移方式、访问标记避免重复、目标状态判定、结果收集与排序。我刷过不少搜索题发现它们几乎都能套用同一个模板定义清晰的状态并思考状态维度能不能压缩设计visited数组或集合维度与状态维度一致选择DFS或BFS初始化起点状态并标记在状态转移前先写transer计算通常是min、max之类目标状态判断放在状态访问后立即执行结果收集用有序结构避免最后手动排序。这个模板解决百题以内的算法训练绰绰有余。可以说Mothers Milk虽然是USACO初级题但它把搜索题的精髓浓缩得非常好。你把它吃透了后面遇到农场灌溉、图像连通域、简单迷宫问题都会觉得似曾相识。6. USACO文件读写的正确提交姿势6.1 从控制台输入切换到文件输入USACO训练系统的老题大多要求从文件读入、向文件输出。以这道题为例输入文件是milk3.in输出文件是milk3.out。在本地开发时用Scanner读控制台很方便但提交前必须改成文件读写。写法如下import java.io.*; import java.util.*; public class milk3 { static int aMax, bMax, cMax; static int milkTotal; static boolean[][] visited; static TreeSetInteger result new TreeSet(); public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new FileReader(milk3.in)); StringTokenizer st new StringTokenizer(br.readLine()); aMax Integer.parseInt(st.nextToken()); bMax Integer.parseInt(st.nextToken()); cMax Integer.parseInt(st.nextToken()); br.close(); milkTotal cMax; visited new boolean[aMax 1][bMax 1]; dfs(0, 0, cMax); PrintWriter out new PrintWriter(new BufferedWriter(new FileWriter(milk3.out))); StringBuilder sb new StringBuilder(); for (int v : result) { sb.append(v).append( ); } out.println(sb.toString().trim()); out.close(); } static void dfs(int a, int b, int c) { // 与前面一致 } }这里要注意类名必须是题目要求的类名。USACO老题通常要求主类名为milk3而不是MotherMilk。如果你在本地IDE里把类名写成了别的提交时忘了改会直接编译错误。我的习惯是本地建立一个专门的提交目录文件内容保持和OJ要求一致测试时用控制台版本确认算法正确后再替换为文件IO版本。6.2 为什么StringTokenizer比split更快在JAVA中读入一行三个整数有人习惯用br.readLine().split( )这当然能工作但StringTokenizer在性能上更优尤其是在老版本的JDK中split会做正则表达式匹配开销比直接分割字符串大不少。虽然这道题只读三个整数差异微乎其微但保持使用StringTokenizer的良好习惯对以后处理大规模输入有好处。不过要提醒的是StringTokenizer在JDK 9之后被标记为不建议使用deprecated但USACO的老编译环境往往还是JDK 8所以这个类依然很实用。如果你在比较新的环境里做题也可以用String[] parts br.readLine().split( )可读性更好。两者都行关键是提交前确认当前OJ的JDK版本。6.3 提交前的自查清单每次准备提交USACO题目时我都有自己的固定检查流程分享给你类名是否正确有没有大小写问题文件读写路径是否正确文件名是否拼错输出是否有多余空格或换行行尾是否需要trim有没有残留的调试输出语句是否把所有static变量都重新初始化防止多测试用例时脏数据数组维度是否加1避免访问容量边界时越界。这套清单看起来琐碎但能省下很多因低级错误导致的罚时。我记得自己第一次提交时就因为输出最后一行的多了一个空格被判了Presentation Error当时还不知道是什么情况查了半天才意识到是格式问题。7. 母牛牛奶还能怎么变着法考7.1 进阶版本求最短倒奶次数如果把题目改成“最少需要倒几次奶才能让A桶为空且C桶为指定值”DFS就不再是最优选择必须上BFS。因为BFS天然按层扩展第一次到达目标状态时经过的步数一定是最少的。这时状态转移和原来一样只是要把每个状态的“层数”也记录下来通常用dist[a][b]数组表示从初始状态到当前状态的最短步数或者用队列里存一个包含步数的数组。这种变形并不难但非常考验对BFS层次遍历的理解。你可以在本地把Mothers Milk改成这个版本试一试比如初始8 9 10问最少几步能让A桶为空时C桶等于9。当你跑出结果并对照手工推导验证时会发现自己对BFS的理解一下子深了不少。7.2 多桶版本状态空间暴涨时的应对如果把三个桶变成四个桶甚至更多状态空间会从二维变成多维visited数组就不好开了。这时必须用状态编码配合HashSet来做去重。比如四个桶的当前奶量可以拼成一个字符串或者按某种编码方式映射成整数。虽然这会让代码复杂不少但思维模式和三个桶版本是相通的定义状态、找转移、查重、收集结果。这类扩展本质上在提醒我们状态压缩不只是面试八股里的概念而是遇到实际性能瓶颈时真正能救命的技巧。做算法题能AC是第一层能理解背后的通用方法才是更高层次的收获。7.3 这个题在面试题里也会出现如果以后准备Java后端面试你可能会发现这类搜索题偶尔会以“三杯水问题”的面目出现在算法面中。面试官不一定会让你写完整代码但会考察你如何分析状态、如何避免重复搜索、如何优化空间。提前把Mothers Milk吃透回答这类问题时就能做到心里有数至少不会现场懵住连DFS和BFS的选择都说不清。所以别小看这道USACO的入门题它背后承载的搜索思维、状态设计、代码模板是可以在很多场景复用的。把一道经典题做深做透远比草草刷十道题更有价值。我自己做题时最大的体会是Mothers Milk的代码可能不到五十行但它逼着我把“状态”这个概念想清楚。状态是什么、怎么转移、怎么判重这三点一旦理顺很多算法题的骨架也就出来了。如果你刚开始刷搜索题我建议不要急着看题解自己先画一画状态转移图再动手写代码哪怕写错了也会留下很深的印象。这份思考的过程才是刷题真正的收获。
