## USACO 1.4 Mother’s Milk 母亲的牛奶（经典的dfs倒水问题）

2018年04月28日 ⁄ 综合 ⁄ 共 1678字 ⁄ 字号 评论关闭

【USACO1.4.4】Mother's Milk 母亲的牛奶

Time Limit:10000MS  Memory Limit:65536K
Total Submit:42 Accepted:27
Case Time Limit:1000MS

Description

Input

Output

Sample Input

```样例输入1：
8 9 10

2 5 10```

Sample Output

```样例输出1:
1 2 8 9 10

5 6 7 8 9 10```

``` /*
ID:wikioi_2
PROG: milk3
LANG: C++
*/
# include<cstdio>
# include<iostream>
# include<cmath>

using namespace std;

# define MAX 21

int A,B,C;
int rec[MAX];
int vis[MAX][MAX][MAX];

void dfs( int a,int b,int c )
{
if ( vis[a][b][c] == 1 )
{
return;
}
else
{
vis[a][b][c] = 1;
}

if ( a==0&&!rec[c] )
{
rec[c] = 1;
}

//c->a
if ( c >= A-a )
{
dfs(A,b,c-A+a);
}
else
{
dfs(a+c,b,0);
}
//c->b
if ( c >= B-b )
{
dfs(a,B,c-B+b);
}
else
{
dfs(a,b+c,0);
}
//b->a
if ( b >= A-a )
{
dfs(A,b-A+a,c);
}
else
{
dfs(a+b,0,c);
}
//b->c
if ( b >= C-c )
{
dfs( a,b-C+c,C);
}
else
{
dfs( a,0,c+b );
}
//a->b
if ( a >= B-b )
{
dfs(a-B+b,B,c);
}
else
{
dfs(0,b+a,c);
}
//a->c
if ( a >= C-c )
{
dfs(a-C+c,b,C);
}
else
{
dfs(0,b,c+a);
}

}

int main(void)
{
freopen("milk3.in","r",stdin);
freopen("milk3.out","w",stdout);
//int A,B,C;
cin>>A>>B>>C;
dfs(0,0,C);
int cnt = 0;
for ( int i = 0;i <= C;i++ )
{
if ( rec[i] )
{
cnt++;
if( cnt == 1 )
{
cout<<i;
}
else
{
cout<<" "<<i;
}
}
}
cout<<endl;

return 0;
}
```