随笔-141  评论-9  文章-3  trackbacks-0
USACO 1.4.4 Mother's Milk


/*
ID: lorelei3
TASK: milk3
LANG: C++
*/
#include <iostream>
#include <fstream>

using namespace std;

const int MAX = 25;

typedef struct State{
    int bucket[3];
}State;

int flag[MAX][MAX][MAX];
int full_bucket[3];
int can[MAX];


State pour(State s, int from, int to){
    
    int amt = s.bucket[from];

    if(s.bucket[to]+amt>full_bucket[to])
        amt = full_bucket[to] - s.bucket[to];
    
    s.bucket[from] -= amt;
    s.bucket[to] += amt;
    return s;
}


void search(State s){

    if(flag[s.bucket[0]][s.bucket[1]][s.bucket[2]])
        return;

    flag[s.bucket[0]][s.bucket[1]][s.bucket[2]] = true;

    if(s.bucket[0] == 0 )
        can[s.bucket[2]] = true;

    for(int i=0; i<3; ++i)
        for(int j=0; j<3; ++j)
            search(pour(s,i,j));
}

int main(){
    
    ifstream in("milk3.in");
    ofstream out("milk3.out");

    in>>full_bucket[0]>>full_bucket[1]>>full_bucket[2];

    State s;
    s.bucket[0] = 0;
    s.bucket[1] = 0;
    s.bucket[2] = full_bucket[2];

    search(s);

    char* sep = "";
    for(int i=0; i<MAX; ++i)
        if(can[i]){
            out<<sep<<i;
            sep=" ";
        }

    out<<endl;

    return 0;
}
posted on 2010-11-09 12:55 小阮 阅读(168) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮