2013年8月14日

UVa 571 - Jugs

#include <cstdio>
#include <string>
#include <queue>
#define MP make_pair
using namespace std;

typedef pair<pair<int, int>, string> State;

int main() {
  int A, B, N;
  while (scanf("%d%d%d", &A, &B, &N) == 3) {
    queue<State> q;
    q.push(MP(MP(0, 0), ""));
    bool vis[1001][1001] = {true};
    while (!q.empty()) {
      int a = q.front().first.first, b = q.front().first.second;
      string path = q.front().second;
      q.pop();
      if (b == N) {
        puts((path + "\nsucess").c_str() + 1);
        break;
      }
      if (!vis[A][b]) {
        vis[A][b] = true;
        q.push(MP(MP(A, b), path + "\nfill A"));
      }
      if (!vis[0][b]) {
        vis[0][b] = true;
        q.push(MP(MP(0, b), path + "\nempty A"));
      }
      if (!vis[a][B]) {
        vis[a][B] = true;
        q.push(MP(MP(a, B), path + "\nfill B"));
      }
      if (!vis[a][0]) {
        vis[a][0] = true;
        q.push(MP(MP(a, 0), path + "\nempty B"));
      }
      int need = A - a;
      int fill = need < b ? need : b;
      if (!vis[a + fill][b - fill]) {
        vis[a + fill][b - fill] = true;
        q.push(MP(MP(a + fill, b - fill), path + "\npour B A"));
      }
      need = B - b;
      fill = need < a ? need : a;
      if (!vis[a - fill][b + fill]) {
        vis[a - fill][b + fill] = true;
        q.push(MP(MP(a - fill, b + fill), path + "\npour A B"));
      }
    }
  }
  return 0;
}

沒有留言:

張貼留言