USACO 1.4.4 Mother's Milk 母親的牛奶 解題報告

Mother's Milk
Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.
Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

PROGRAM NAME: milk3

INPUT FORMAT

A single line with the three integers A, B, and C.

SAMPLE INPUT (file milk3.in)

8 9 10

OUTPUT FORMAT

A single line with a sorted list of all the possible amounts of milk that can be in bucket C when bucket A is empty.

SAMPLE OUTPUT (file milk3.out)

1 2 8 9 10

SAMPLE INPUT (file milk3.in)

2 5 10

SAMPLE OUTPUT (file milk3.out)

5 6 7 8 9 10

【中文翻譯】 

描述

農民約翰有三個容量分別是A,B,C升的桶，A,B,C分別是三個從1到20的整數，

最初，A和B桶都是空的，而C桶是裝滿牛奶的。有時，約翰把牛奶從一個桶倒到另一個桶中，直到被灌桶裝滿或原桶空了。當然每一次灌注都是完全的。由於節約，牛奶不會有丟失。

寫一個程序去幫助約翰找出當A桶是空的時候，C桶中牛奶所剩量的所有可能性。

格式

PROGRAM NAME: milk3

INPUT FORMAT:

(file milk3.in)

單獨的一行包括三個整數A,B和C。

OUTPUT FORMAT:

(file milk3.out)

只有一行，升序地列出當A桶是空的時候，C桶牛奶所剩量的所有可能性。

SAMPLE INPUT 1

8 9 10

SAMPLE OUTPUT 1

1 2 8 9 10

SAMPLE INPUT 2

2 5 10

SAMPLE OUTPUT 2

5 6 7 8 9 10

 

【分析】

 由於數據規模很小，可以用dfs+哈希判重。

遞歸函數有3個參數a,b,c，分別表示A、B、C這三個桶中牛奶的剩餘量。

一共有6種可能的移動方式：

1. A->B

2. A->C

3. B->A

4. B->C

5. C->A

6. C->B 

有一些顯而易見的減枝，如當一個桶的剩餘量大於0時才倒出等。 

可以開一個三維bool型數組用來判重。

當然，結果也可以用哈希數組來存儲。 

當a==0時記錄下這時c的值，最後從小到大輸出所有可能的c值即可。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
bool flag[21][21][21];
int rs[21];
int A,B,C;


int Min(int a,int b)
{
 if(b<a)
  a=b;
 return a;
}

void init()
{
 scanf("%d %d %d\n",&A,&B,&C);
 for (int i=1;i<=C;i++)
  for(int j=1;j<=C;j++)
   for (int k=1;k<=C;k++)
    flag[i][j][k]=false;
 for (int i=1;i<=C;i++)
  rs[i]=false;
 return;
}

void dfs(int a,int b,int c)
{
 flag[a][b][c]=true;
 //cout<<a<<" "<<b<<" "<<c<<endl;
 
 if(a==0)
  rs[c]=true;
 
 int ta,tb,tc;
 if(a>0)
 {
  //a->b
  int t=Min(a,B-b);
  ta=a-t;
  tb=b+t;
  tc=c;
  if(!flag[ta][tb][tc])
   dfs(ta,tb,tc);
  
  //a->c
  t=Min(a,C-c);
  ta=a-t;
  tb=b;
  tc=c+t;
  if(!flag[ta][tb][tc])
   dfs(ta,tb,tc);
 }
  
 if(b>0)
 {
  //b->a
  int t=Min(b,A-a);
  ta=a+t;
  tb=b-t;
  tc=c; 
  if(!flag[ta][tb][tc])
   dfs(ta,tb,tc);
  
  //b->c
  t=Min(b,C-c);
  ta=a;
  tb=b-t;
  tc=c+t;
  if(!flag[ta][tb][tc])
   dfs(ta,tb,tc);
 }
 
 if(c>0)
 {
  //c->a
  int t=Min(c,A-a);
  ta=a+t;
  tb=b;
  tc=c-t;
  if(!flag[ta][tb][tc])
   dfs(ta,tb,tc);
  
  //c->b
  t=Min(c,B-b);
  ta=a;
  tb=b+t;
  tc=c-t;
  if(!flag[ta][tb][tc])
   dfs(ta,tb,tc);
 }
 
}

int main()
{
 freopen("milk3.in","r",stdin);
 freopen("milk3.out","w",stdout);
 init();
 dfs(0,0,C);
 for (int i=0;i<=C;i++)
  if(rs[i])
   cout<<i<<" ";
 return 0;
}
 

【評測結果】 

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	281 KB	0
2	正确	10	0.000 s	281 KB	0
3	正确	10	0.000 s	281 KB	0
4	正确	10	0.000 s	281 KB	0
5	正确	10	0.000 s	281 KB	0
6	正确	10	0.000 s	281 KB	0
7	正确	10	0.000 s	281 KB	0
8	正确	10	0.000 s	281 KB	0
9	正确	10	0.000 s	281 KB	0
10	正确	10	0.000 s	281 KB	0

运行完成
运行时间 0.003 s
平均内存使用 281 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!