|
Posted on 2007-05-31 17:17 ZelluX 阅读(700) 评论(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->a == 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;
}

|