SSL JudgeOnline 1099——USACO 1.4 母亲的牛奶

Description

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

Input

单独的一行包括三个整数A,B和C。

Output

只有一行，列出当A桶是空的时候，C桶牛奶所剩量的所有可能性。

Sample Input

样例1
8 9 10

样例2
2 5 10

Sample Output

样例1
1 2 8 9 10

样例2
5 6 7 8 9 10

---

这题直接dfs,倒奶只有六种情况：
A-B B-A A-C C-A B-C C-B
每一种情况都搜一次，最后输出（要从0开始）

---

代码如下：

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

function min(x,y:longint):longint;
begin
  if x>y then exit(y)
         else exit(x);
end;

procedure dg(ma,mc:longint);
var mb:longint;
begin
  if f[ma,mc] then exit;
  f[ma,mc]:=true;
  mb:=abs(c-ma-mc);
  dg(ma-min(ma,b-mb),mc);
  dg(ma-min(ma,c-mc),mc+min(ma,c-mc));
  dg(ma,mc+min(mb,c-mc));
  dg(ma+min(mb,a-ma),mc);
  dg(ma+min(mc,a-ma),mc-min(mc,a-ma));
  dg(ma,mc-min(mc,b-mb));
end;

begin
  read(a,b,c);
  fillchar(f,sizeof(f),false);
  dg(0,c);
  for i:=0 to c do if f[0,i] then write(i,' ');
end.