|
|
Posted on 2007-05-31 17:17 ZelluX 閱讀(705) 評論(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;
}
|