USACO1.4 母亲的牛奶 Mother's Milk

母亲的牛奶

题目描述

农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数， 最初，A和B桶都是空的，而C桶是装满牛奶的。有时，农民把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。

写一个程序去帮助农民找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。

分析：搜索每种可能，搜索变量只用表示AC两个桶中牛奶剩余数量，因为题目只要求AC两桶数量，B桶计算可得，共有6种情况AC,AB,BA,BC,CA,CB，根据变化情况搜索，f数组判重，搜过的情况直接退出。

代码

var
  f:array[0..20,0..20] of boolean;
  a,b,c,i:longint;


procedure dfs(x,z:longint);
var
  y:longint;
begin
  if f[x,z] then exit;
  y:=c-x-z;
  f[x,z]:=true;
  if x>0 then
    begin
      if y<b then
        if b-y>=x then dfs(0,z) else dfs(x-(b-y),z);
      if z<c then
        if c-z>=x then dfs(0,z+x) else dfs(x-(c-z),c);
    end;
  if y>0 then
    begin
      if x<a then
        if a-x>=y then dfs(x+y,z) else dfs(a,z);
      if z<c then
        if c-z>=y then dfs(x,z+y) else dfs(x,c);
    end;
  if z>0 then
    begin
      if x<a then
        if a-x>=z then dfs(x+z,0) else dfs(a,z-(a-x));
      if y<b then
        if b-y>=z then dfs(x,0) else dfs(x,z-(b-y));
    end;
end;


begin
  readln(a,b,c);
  dfs(0,c);
  for i:=0 to c do
    if f[0,i] then write(i,' ');
end.