[USACO][Section 1.4][搜索] Mother’s Milk

题目大意：

给出三个容量分别为A、B、C的桶。开始时只有容量为C的桶中有奶且装满，可以将一个桶中的奶倒入另一个桶，问当容量为A的桶为空时，容量为C的桶内可能有多少奶。

思路：

简单深搜，具体思路见代码。

代码：

/*
ID: lujunda1
LANG: C++
PROG: milk3
*/
#include
#include
using namespace std;
int cap[3];
//三个桶的容量。 
bool map[21][21][21],res[21];
//map[]用来记录状态。
//res[]记录当A桶空时，C桶内的牛奶的数量。 
void pour(int i,int j,int state[])
//将第i桶倒入第j桶中。
//state[]是表示各桶内牛奶的数量。 
{
    if(cap[j]-state[j]>=state[i])
    //i桶可以全部倒入j桶 
    {
        state[j]+=state[i];
        state[i]=0;        
    }
    else
    //i桶只能部分倒入j桶 
    {
        state[i]-=(cap[j]-state[j]);
        state[j]=cap[j];
    }
}
void dfs(int a,int b,int c)
//使用深搜遍历所有状态。 
{
    map[a][b][c]=true;
    if(a==0)
        res[c]=true;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(i!=j)
            {
                int state[3]={a,b,c};
                pour(i,j,state);
                if(!map[state[0]][state[1]][state[2]])
                    dfs(state[0],state[1],state[2]);
            }
}
void restore()
//对res[]和map[]进行初始化。 
{
    for(int i=0;i<21;i++)
    {
        res[i]=false;
        for(int j=0;j<21;j++)
            for(int k=0;k<21;k++)
                map[i][j][k]=false;
    }
}
void output()
//根据res[]输出结果。 
{
    bool check=false;
    for(int i=0;i<=cap[2];i++)
    {
        if(res[i]&&!check)
        {
            printf("%d",i);
            check=true;
        }
        else if(res[i])
            printf(" %d",i);
    }
    printf("\n"); 
}
int main()
{
    freopen("milk3.in","r",stdin);
    freopen("milk3.out","w",stdout);
    for(int i=0;i<3;i++)
        scanf("%d",&cap[i]);
    restore();
    dfs(0,0,cap[2]);
    output();
}