POJ 1606 Jugs

問題

ビーカーAとBの容量Ca、Cbが与えられる。ビーカーに水を入れる操作を行って、どちらかのビーカーに入っている水がNになるようにしたい。行ってよい操作は以下の6種類である。

• Aいっぱいに水を入れる
• Bいっぱいに水を入れる
• Aを空にする
• Bを空にする
• Aの水をBに入れる（Aが空になるかBが満杯になるまで）
• Bの水をAに入れる（Bが空になるかAが満杯になるまで）

かならず達成できるような入力が与えられるので達成するまでの操作を出力せよ。達成方法が複数ある場合は任意の1パターンを出力せよ。

やりかた

AとBのビーカーの水の量を状態として持たせたメモ化再帰で十分通った。

以下ソース。

int ca, cb, n;
bool memo[1001][1001];
deque<int> ans;

void rec(int a, int b, deque<int> t /* 操作の履歴 */){
  if(a == n || b == n){
    ans = t;
    return;
  }
  if(!ans.empty() || memo[a][b]) return;
  memo[a][b] = true;
  if(a != ca){
    t.push_back(0);
    rec(ca, b, t); // fill A
    t.pop_back();
  }
  if(b != cb){
    t.push_back(1);
    rec(a, cb, t); // fill B
    t.pop_back();
  }
  if(a != 0){
    t.push_back(2);
    rec(0, b, t); // empty A
    t.pop_back();
    t.push_back(4);
    int chg = min(a, cb - b);
    rec(a - chg, b + chg, t); //pour A B
    t.pop_back();
  }
  if(b != 0){
    t.push_back(3);
    rec(a, 0, t); // empty B
    t.pop_back();
    t.push_back(5);
    int chg = min(b, ca - a);
    rec(a + chg, b, t); //pour B A
    t.pop_back();
  }
  return;
}
string str[] = {
  "fill A", "fill B", "empty A", "empty B", 
  "pour A B", "pour B A",
};
int main(int argc, char **argv){
  while(cin >> ca >> cb >> n){
    FILL(memo, false);
    ans.clear();
    rec(0, 0, deque<int>());
    deque<int>::iterator it = ans.begin();
    for(; it != ans.end(); it++) cout << str[*it] << endl;
    cout << "success" << endl;
  }
  return 0;
}