UVa 571 - Jugs

// UVa 571 - Jugs

#include <iostream>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;

string move[6] = { "fill A", "fill B", "empty A", "empty B", "pour A B", "pour B A" };

struct state {
	int a, b;
};

int T[1001][1001];
state R[1001][1001];
int sa, sb;
int oo;
int ca, cb, n;
queue<state> q;

bool check(int a1, int b1, int move, int a, int b) {
	if (T[a1][b1] == oo) {
		T[a1][b1] = move;
		state st = { a, b };
		R[a1][b1] = st;
		state st1 = { a1, b1 };
		q.push(st1);
		if (b1 == n) {
			sa = a1;
			sb = b1;
			return true;
		}
	}
	return false;
}

int main() {

	while (cin >> ca >> cb >> n) {

		memset(T, 255, sizeof(T));
		oo = T[0][0];
		T[0][0] = 6;
		q = queue<state>();
		state ini = { 0, 0 };
		q.push(ini);
		sa = 0;
		sb = 0;

		while (!q.empty()) {
			int a = q.front().a;
			int b = q.front().b;
			q.pop();
			// fill A
			int a1 = ca;
			int b1 = b;
			if (check(a1, b1, 0, a, b))
				break;
			// fill B
			a1 = a;
			b1 = cb;
			if (check(a1, b1, 1, a, b))
				break;
			// empty A
			a1 = 0;
			b1 = b;
			if (check(a1, b1, 2, a, b))
				break;
			// empty B
			a1 = a;
			b1 = 0;
			if (check(a1, b1, 3, a, b))
				break;
			// pour A B
			int m = min(a, cb - b);
			a1 = a - m;
			b1 = b + m;
			if (check(a1, b1, 4, a, b))
				break;
			// pour B A
			m = min(ca - a, b);
			a1 = a + m;
			b1 = b - m;
			if (check(a1, b1, 5, a, b))
				break;
		}

		vector<int> sol;
		int a = sa;
		int b = sb;
		while (a || b) {
			sol.push_back(T[a][b]);
			int aa = R[a][b].a;
			b = R[a][b].b;
			a = aa;
		}

		for (int i = sol.size() - 1; i >= 0; i--)
			cout << move[sol[i]] << endl;
		cout << "success" << endl;

	}

	return 0;
}