Mother's Milk（DFS）

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三个瓶子的容积，一开始为0,0,C（C为满）的状态。随后互相可以倒牛奶，每次倒都是一次倒完，或者倒满容器为止。求当A=0时，C牛奶容积的可能性。从小到大输出结果。

 

   思路：

   dfs。标记六种倒的过程，分别为A倒B，A倒C，B倒A，B倒C，C倒A，C倒B。用vis数组标记每种状态是否曾经到达过。最后将A==0时候C的数存到num数组中，最后输出vis数组即可。

 

   AC：

/*  
TASK:milk3  
LANG:C++  
ID:sum-g1  
*/ 
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int res[25],ans,a,b,c,vis[20][20][20];

void dfs(int na,int nb,int nc)
{
    if(vis[na][nb][nc]) return;
    vis[na][nb][nc]=1;   //标记状态
    if(!na)   //判断不是!na&&nc,nc可以为0
    {
        ans++;
        res[ans]=nc;
    }
    if(na&&nb!=b)
    {
        if(b-nb>=na)  dfs(0,na+nb,nc);
        else          dfs(na+nb-b,b,nc);
    }
    if(na&&nc!=c)
    {
        if(c-nc>=na)  dfs(0,nb,na+nc);
        else          dfs(na+nc-c,nb,c);
    }
    if(nb&&na!=a)
    {
        if(a-na>=nb)  dfs(na+nb,0,nc);
        else          dfs(a,nb+na-a,nc);
    }
    if(nb&&nc!=c)
    {
        if(c-nc>=nb)  dfs(na,0,nc+nb);
        else          dfs(na,nb+nc-c,c);
    }
    if(nc&&na!=a)
    {
        if(a-na>=nc)  dfs(na+nc,nb,0);
        else          dfs(a,nb,nc+na-a);
    }
    if(nc&&nb!=b)
    {
        if(b-nb>=nc)  dfs(na,nb+nc,0);
        else          dfs(na,b,nc+nb-b);
    }
}

int main()
{
    freopen("milk3.in","r",stdin);    
    freopen("milk3.out","w",stdout);  
    ans=0;
    memset(res,0,sizeof(res));
    memset(vis,0,sizeof(vis));
    scanf("%d%d%d",&a,&b,&c);
    dfs(0,0,c);
    sort(res+1,res+1+ans);
    for(int i=1;i<=ans;i++)
    {
        printf("%d",res[i]);
        i==ans?printf("\n"):printf(" ");
    }
    return 0;
}

 

    总结：

    1.应该标记的是a,b,c的状态，而不是标记曾经走过哪个过程，标记过程会导致重复搜索，比如a->b，b->a则会返回去原来的状态；

    2.c的状态可能为0；