USACO Mother's Milk

题意 ：有3个杯子，问当a杯子为空时，c杯子能够装多少种体积的水

思路 ：倒水问题，有广搜，对于当前，接下来有6种状态：a到给b，a到给c ,c到给b,c到给a,b到给a, b到给c。每一种状态又有两种情况：能装满和不能装满。这里还要注意一点就是必须判断重复，即防止a倒给b，然后b再倒给a这种情况的发生！

这里还有一个节省代码的技巧：因为情况很多，一开始我使用6个if，结果代码写的老长，十分不方便debug。我们可以使用for循环，在控制是哪个杯子时我是用了模运算，具体实现请看代码，我觉得写的还不错哦！

代码：

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cstdio>
#define N 29

using namespace std;

bool v[N][N];
typedef struct
{
    int w[3];
}milk;

int bfs( milk start, int *ans )
{
    int times = 0;
    milk now;
    now.w[0] = now.w[1] = 0;
    now.w[2] = start.w[2];
    queue <milk> q;
    memset( v, false, sizeof( v ) );
    v[0][0] = true;
    q.push( now );
    while( !q.empty() )
    {
        now = q.front();
        q.pop();
        milk t;
        for( int i = 0; i < 3; i++ )
        {
            if( now.w[i] > 0 )
            {
                for( int j = i + 1; j < i + 3; j++ )
                {
                    t = now;
                    if( now.w[i] >= start.w[j%3] - now.w[j%3] )
                    {
                        t.w[i] = now.w[i] - ( start.w[j%3] - now.w[j%3] );
                        t.w[j%3] = start.w[j%3];
                    }
                    else
                    {
                        t.w[i] = 0;
                        t.w[j%3] = now.w[j%3] + now.w[i];
                    }
                    if( !v[t.w[0]][t.w[1]] )
                    {
                        if( t.w[0] == 0 )
                        {
                            ans[times++] = t.w[2];
                        }
                        v[t.w[0]][t.w[1]] = true;
                        q.push( t );
                    }
                }
            }
        }
    }
    return times;
}

int main()
{
    freopen( "milk3.in", "r", stdin );
    freopen( "milk3.out", "w", stdout );
    milk start;
    while( cin >> start.w[0] >> start.w[1] >> start.w[2] )
    {
        int ans[N];
        int times = bfs( start, ans );
        sort( ans, ans + times );
        for( int i = 0; i < times; i++ )
        {
            cout << ans[i] << ‘ ‘;
        }
        cout << start.w[2] << ‘\n‘;
    }
    return 0;
}

USACO Mother's Milk,布布扣,bubuko.com

USACO Mother's Milk

原文：http://blog.csdn.net/u011564456/article/details/23353719