UVa 571 - Jugs

Accepted date: 2011-12-20
Ranking (as of 2013-06-15): 670 out of 1520
Language: C++

/*
  UVa 571 - Jugs

  To build using Visual Studio 2008:
    cl -EHsc -O2 jugs.cpp
*/

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

enum {fill_A, fill_B, empty_A, empty_B, pour_A_B, pour_B_A};

struct jugs {
  int a_, b_;
  stack<char> steps_;

  jugs(int a, int b, char s) : a_(a), b_(b) {steps_.push(s);}
  jugs(int a, int b, char s, const stack<char>& steps) : a_(a), b_(b),
    steps_(steps) {steps_.push(s);}
};

void print_steps(stack<char>& steps)
{
  const char* instructions[] = {"fill A\n", "fill B\n",
    "empty A\n", "empty B\n", "pour A B\n", "pour B A\n"};
  if (!steps.empty()) {
    char s = steps.top(); steps.pop();
    print_steps(steps);
    cout << instructions[s];
  }
}

bool push_jugs_state(int a, int b, char s, const stack<char>& steps,
  vector< vector<bool> >& states, queue<jugs>& q)
{
  if (!states[a][b]) {
    states[a][b] = true;
    q.push(jugs(a, b, s, steps));
    return true;
  }
  else
    return false;
      // do not transfer to the state that has already been transferred before
}

void pour_jugs(int ca, int cb, int n)
{
  vector< vector<bool> > states(ca + 1, vector<bool>(cb + 1, false));
    // states[i][j] is true if the state where the content of A is i and 
    // the content of B is j has already been examined
  queue<jugs> q;
  if (ca > n) {
    states[ca][0] = true;
    q.push(jugs(ca, 0, fill_A));
  }
  else {
    states[0][cb] = true;
    q.push(jugs(0, cb, fill_B));
  }
  for ( ; !q.empty(); q.pop()) {
    jugs& j = q.front();
    if (j.b_ == n) {
      print_steps(j.steps_);
      break;
    }
    int a, b, p;
    // if either of the jugs is empty, try pouring to the empty jug, 
    // or fill the empty jug
    if (!j.a_) {
      p = min(ca, j.b_);
      push_jugs_state(p, j.b_ - p, pour_B_A, j.steps_, states, q);
      if (j.b_ < cb)
        push_jugs_state(ca, j.b_, fill_A, j.steps_, states, q);
    }
    else if (!j.b_) {
      p = min(j.a_, cb);
      push_jugs_state(j.a_ - p, p, pour_A_B, j.steps_, states, q);
      if (j.a_ < ca)
        push_jugs_state(j.a_, cb, fill_B, j.steps_, states, q);
    }
    // if both of the jugs are not empty, try pouring between jags, 
    // or empty the fully-filled jug
    else {
      if (j.a_ < ca) {
        p = min(ca - j.a_, j.b_);
        push_jugs_state(j.a_ + p, j.b_ - p, pour_B_A, j.steps_, states, q);
      }
      else if (j.a_ == ca)
        push_jugs_state(0, j.b_, empty_A, j.steps_, states, q);
      if (j.b_ < cb) {
        p = min(cb - j.b_, j.a_);
        push_jugs_state(j.a_ - p, j.b_ + p, pour_A_B, j.steps_, states, q);
      }
      else if (cb == j.b_)
        push_jugs_state(j.a_, 0, empty_B, j.steps_, states, q);
    }
  }
  cout << "success\n";
}

int main()
{
  int ca, cb, n;
  while (cin >> ca >> cb >> n)
    pour_jugs(ca, cb, n);
  return 0;
}