#include<stdio.h>
#define MAX_QUEUE 100000
#define TARGET 3
#define A_VOLUMN 5
#define B_VOLUMN 6
#define min(a,b) (a) < (b) ? (a) : (b)
struct state {
int bottleA; /* Remained water in bottle A */
int bottleB; /* Remained water in bottle B */
int action; /* How this state is achieved from its father state */
int father; /* Where this state is transfered from */
};
enum Action {
FILL_A, /* Fill A with full water */
FILL_B, /* Fill B with full water */
A_TO_B, /* Pour the water from A to B */
B_TO_A, /* Pour the water from B to A */
POUR_A, /* Pour all the water from A to the pool to make it empty*/
POUR_B, /* Pour all the water from B to the pool to make it empty*/
NONE /* NONE ACTION */
};
struct state queue[MAX_QUEUE]; /* The search Queue*/
int head; /* The head of the search queue */
int tail; /* The tail of the search queue */
int success = 0; /* Whether the search has succeed */
int flag; /* This will record the target position in the queue*/
short checked[A_VOLUMN + 1][B_VOLUMN + 1] = {0};
/**
* Initialize the search queue, insert the first state
*/
void init() {
head = 0;
tail = 1;
queue[0].bottleA = 0;
queue[0].bottleB = 0;
queue[0].father = 0;
queue[0].action = NONE;
checked[0][0] = 1;
}
void update(int a, int b, enum Action action) {
/* If this state is checked, ignore it */
if (checked[a][b])
return;
/* Record the state in the queue and check it */
queue[tail].bottleA = a;
queue[tail].bottleB = b;
queue[tail].action = action;
queue[tail].father = head;
checked[a][b] = 1;
/* If we have arrived at the target, record the tail for backtracing the result */
if (a == TARGET || b == TARGET) {
success = 1;
flag = tail;
}
tail++;
}
void generateStates() {
int transfered_water;
/* Fullfill the bottle A */
update(A_VOLUMN, queue[head].bottleB, FILL_A);
/* Fullfill the bottle B */
update(queue[head].bottleA, B_VOLUMN, FILL_B);
/* Transfer water from A to B */
transfered_water = min(queue[head].bottleA, B_VOLUMN - queue[head].bottleB);
update(queue[head].bottleA - transfered_water, queue[head].bottleB + transfered_water, A_TO_B);
/* Transfer water from B to A */
transfered_water = min(queue[head].bottleB, A_VOLUMN - queue[head].bottleA);
update(queue[head].bottleA + transfered_water, queue[head].bottleB - transfered_water, B_TO_A);
/* Empty Bottle A */
update(0, queue[head].bottleB, POUR_A);
/* Empty Bottle B */
update(queue[head].bottleA, 0, POUR_B);
}
void work() {
while(!success && head != tail) {
generateStates();
head++;
};
}
void backtraceResult(int pointer) {
if (pointer == 0)
return;
else
backtraceResult(queue[pointer].father);
static char* actions[] = {"Fill A with full water from the pool -> ",
"Fill B with full water from the pool -> ",
"Pour the water from A to B -> ",
"Pour the water from B to A -> ",
"Empty bottle A -> ",
"Empty bottle B -> "};
printf("%s A:%3d B:%3d\n", actions[queue[pointer].action], queue[pointer].bottleA, queue[pointer].bottleB);
}
void printResult() {
if (!success) {
printf("Cannot search out the result!\n");
return;
}
/* Print the initial state */
printf("Start with A: 0 B: 0\n");
/* Backtrace to output all states leading to the solution */
backtraceResult(flag);
/* Print a success to indicate we achieved our goal */
printf("Success!\n");
}
int main() {
init();
work();
printResult();
return 0;
}