UVA 10603 Fill【BFS】

题意

有三个给定容量的没有刻度的杯子，其中一个杯子装满水，问量出给定水的体积需要倒多少水（倒水时水量的和）

分析

直接BFS，但非常容易写错

AC代码

//UVA 10603 Fill
//AC 2016-07-19 16:11:16
//BFS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <list>
#include <sstream>
#include <stack>
using namespace std;

#define cls(x) memset(x,0,sizeof x)
#define inf(x) memset(x,0x3f,sizeof x)
#define neg(x) memset(x,-1,sizeof x)
#define ninf(x) memset(x,0xc0,sizeof x)
#define st0(x) memset(x,false,sizeof x)
#define st1(x) memset(x,true,sizeof x)
#define INF 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define bug cout<<"here"<<endl;
//#define debug

int C[3];
int total;
int visit[300][300];

struct node
{
    int va;
    int vb;
    int pour;
    node(){}
    node(int a,int b,int p):va(a),vb(b),pour(p){}
}p;

queue<node> BFS;

int main()
{
    #ifdef debug
        freopen("E:\Documents\code\input.txt","r",stdin);
        freopen("E:\Documents\code\output.txt","w",stdout);
    #endif
    int N;
    int goal;
    scanf("%d",&N);
    while(N--)
    {
        scanf("%d %d %d %d",&C[0],&C[1],&C[2],&goal);
        total=C[2];
        inf(visit);
        while(BFS.size())
            BFS.pop();
        int V[3];
        int change;
        BFS.push(node(0,0,0));
        while(BFS.size())
        {
            p=BFS.front();
            BFS.pop();
            if(p.pour>=visit[p.va][p.vb])
                continue;
            visit[p.va][p.vb]=p.pour;
            for(int i=0;i<3;++i)
            {
                for(int j=0;j<3;++j)
                {
                    V[0]=p.va;
                    V[1]=p.vb;
                    V[2]=total-p.va-p.vb;
                    if(i==j||V[i]==0||V[j]==C[j])
                        continue;
                    if(V[i]>C[j]-V[j])
                        change=C[j]-V[j];
                    else
                        change=V[i];
                    //cout<<V[i]<<"&&"<<V[j]<<endl;
                    V[i]-=change;
                    V[j]+=change;
                    //cout<<i<<"--"<<j<<"**"<<change<<"&&&"<<p.pour<<endl;
                    //cout<<V[i]<<"###"<<V[j]<<endl;
                    if(visit[V[0]][V[1]]>p.pour+change)
                        BFS.push(node(V[0],V[1],p.pour+change));
                }
            }
        }
        int res;
        for(;;--goal)
        {
            res=INF;
            for(int i=0;i<=total-goal;++i)
            {
                res=min(res,visit[i][goal]);
                res=min(res,visit[goal][i]);
                res=min(res,visit[total-i-goal][i]);
            }
            if(res<INF)
                break;
        }
        printf("%d %d
",res,goal);
    }
    return 0;
}