Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

USACO 1.1.4 Mother's Milk

Posted on 2007-05-31 17:17 ZelluX 阅读(581) 评论(0)  编辑  收藏 所属分类: Algorithm
BFS,一次通过
/*
PROG: milk3
ID: 06301031
LANG: C++
*/


#include 
<iostream>
#include 
<fstream>
#include 
<deque>
#include 
<set>

using namespace std;

struct Status {
    
int a;
    
int b;
    
int c;
}
;

void pour(const int from, const int to, const int maxTo, int& newFrom, int& newTo) {
    newTo 
= from + to;
    newFrom 
= 0;
    
if (newTo > maxTo) {
        newFrom 
= newTo - maxTo;
        newTo 
= maxTo;
    }

}


int main() {
    
int i, j, k;
    ifstream fin(
"milk3.in");
    ofstream fout(
"milk3.out");
    Status begin;
    
int maxA, maxB, maxC;
    fin 
>> maxA >> maxB >> maxC;
    begin.a 
= 0;
    begin.b 
= 0;
    begin.c 
= maxC;
    
    
bool hash[21][21][21];
    
for (i = 0; i <= maxA; i++{
        
for (j = 0; j <= maxB; j++{
            
for (k = 0; k <= maxC; k++{
                hash[i][j][k] 
= false;
            }

        }

    }

    hash[
0][0][maxC] = true;
    
set<int> result;

    deque
<Status> queue;
    queue.push_back(begin);
    
while (!queue.empty()) {
        deque
<Status>::iterator now = queue.begin();
        
if (now->== 0{
            result.insert(now
->c);
        }

        Status newStat;
        newStat 
= *now;
        pour(now
->a, now->b, maxB, newStat.a, newStat.b);
        
if (!hash[newStat.a][newStat.b][newStat.c]) {
            hash[newStat.a][newStat.b][newStat.c] 
= true;   
            queue.push_back(newStat);
        }

        newStat 
= *now;
        pour(now
->b, now->a, maxA, newStat.b, newStat.a);
        
if (!hash[newStat.a][newStat.b][newStat.c]) {
            hash[newStat.a][newStat.b][newStat.c] 
= true;
            queue.push_back(newStat);
        }

        newStat 
= *now;
        pour(now
->c, now->a, maxA, newStat.c, newStat.a);
        
if (!hash[newStat.a][newStat.b][newStat.c]) {
            hash[newStat.a][newStat.b][newStat.c] 
= true;
            queue.push_back(newStat);
        }

        newStat 
= *now;
        pour(now
->a, now->c, maxC, newStat.a, newStat.c);
        
if (!hash[newStat.a][newStat.b][newStat.c]) {
            hash[newStat.a][newStat.b][newStat.c] 
= true;
            queue.push_back(newStat);
        }

        newStat 
= *now;
        pour(now
->b, now->c, maxC, newStat.b, newStat.c);
        
if (!hash[newStat.a][newStat.b][newStat.c]) {
            hash[newStat.a][newStat.b][newStat.c] 
= true;
            queue.push_back(newStat);
        }

        newStat 
= *now;
        pour(now
->c, now->b, maxB, newStat.c, newStat.b);
        
if (!hash[newStat.a][newStat.b][newStat.c]) {
            hash[newStat.a][newStat.b][newStat.c] 
= true;
            queue.push_back(newStat);
        }


        queue.pop_front();
    }


    
set<int>::iterator iter = result.begin();
    fout 
<< *iter;
    iter
++;
    
for (; iter != result.end(); iter++{
        fout 
<< " " << *iter;
    }

    fout 
<< endl;
    
return 0;
}


只有注册用户登录后才能发表评论。


网站导航: