Skip to content

Instantly share code, notes, and snippets.

@james0zan
Created June 15, 2013 06:11
Show Gist options
  • Save james0zan/5787118 to your computer and use it in GitHub Desktop.
Save james0zan/5787118 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <string.h>
#include <queue>
#include <string>
using namespace std;
#define mp make_pair
#define pb push_back
int dp[100][100], done[100];
pair<int, int> last[100][100];
string op[100][100];
vector<string> my[100];
void trace(int R, int B, int c) {
my[c].clear();
while (R != 0 || B != 0) {
int tR = last[R][B].first;
int tB = last[R][B].second;
my[c].pb(op[R][B]);
R = tR; B = tB;
}
}
void solve(int R, int B) {
dp[0][0] = 1;
queue<pair<int, int> > Q;
Q.push(mp(0, 0));
while (! Q.empty()) {
pair<int, int> temp = Q.front(); Q.pop();
int a = temp.first;
int b = temp.second;
if (a > 0) {
if (dp[0][b] == 0) {
dp[0][b] = 1;
op[0][b] = "empty red jug";
last[0][b] = mp(a, b);
Q.push(mp(0, b));
}
}
if (b > 0) {
if (dp[a][0] == 0) {
dp[a][0] = 1;
op[a][0] = "empty blue jug";
last[a][0] = mp(a, b);
Q.push(mp(a, 0));
}
}
if (a < R && b > 0) {
int m = min(R - a, b);
if (dp[a+m][b-m] == 0) {
dp[a+m][b-m] = 1;
op[a+m][b-m] = "pour blue jug into red jug";
last[a+m][b-m] = mp(a, b);
Q.push(mp(a+m, b-m));
}
}
if (b < B && a > 0) {
int m = min(B - b, a);
if (dp[a-m][b+m] == 0) {
dp[a-m][b+m] = 1;
op[a-m][b+m] = "pour red jug into blue jug";
last[a-m][b+m] = mp(a, b);
Q.push(mp(a-m, b+m));
}
}
if (a < R) {
if (dp[R][b] == 0) {
dp[R][b] = 1;
op[R][b] = "fill red jug";
last[R][b] = mp(a, b);
Q.push(mp(R, b));
}
}
if (b < B) {
if (dp[a][B] == 0) {
dp[a][B] = 1;
op[a][B] = "fill blue jug";
last[a][B] = mp(a, b);
Q.push(mp(a, B));
}
}
}
for (int i=0; i<=R; i++) {
for (int j=0; j<=B; j++) {
if (done[i] == 0) {
done[i] = 1;
trace(i, j, i);
//my[i]=(new vecotr<string>(trace(i, j)));
}
if (done[j] == 0) {
done[j] = 1;
trace(i, j, j);
//my[j]=(new vecotr<string>(trace(i, j)));
}
}
}
for (int i=1; i<=max(R, B); i++) {
if (done[i]) {
int j;
printf("%d\n", i);
for (j=my[i].size()-1; j>=0; j--) {
printf("%s\n", my[i][j].c_str());
}
}
}
}
int main() {
int A, B;
memset(dp, 0, sizeof(dp));
memset(done, 0, sizeof(done));
scanf("%d%d", &A, &B);
solve(A, B);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment