# UOJ CUP : Breadth First Search (BFS)

You are given two cups that can hold exactly X and Y litres of water respectively. These two cups have no markings. You also have an unlimited supply of water.

You can only perform the following actions:

• Fill a cup with water to its maximum volume.
• Empty a cup.
• Pour water from one cup to the other (until either the receiving cup is full or the pouring cup is empty).

Your task is find the minimum number of actions needed to measure out a given volume V of water using only these two cups. Your cups are always empty at the start.

Input

The first and only line of input contains three integer, X, Y, and V, in that order.

Output

Print the minimum number of actions needed, or `-1` if it is impossible to achieve V.

Problem Source: UTP Online Judge

I think we should use Breadth First Search instead of Depth First Search because the first solution we seek from DFS cannot guarantee that it is the minimal step but BFS can.

First, we see the solution:

C++

```#include <iostream>
#include <queue>

using namespace std;

int main() {

int X, Y, V;
cin >> X >> Y >> V;

int step[X+1][Y+1];
for (int i=0; i<=X; i++){
for (int j=0; j<=Y; j++){
step[i][j] = -1;
}
}
step[0][0] = 0;
step[X][Y] = 0;

queue<int> qx;
queue<int> qy;

qx.push(X); qx.push(0);
qy.push(0); qy.push(Y);

bool found = false;
int j = 1;
while(!qx.empty() && !found){
int len = qx.size();
for (int i=0; i<len; i++){
int cupA = qx.front(); qx.pop();
int cupB = qy.front(); qy.pop();

if (step[cupA][cupB] != -1) continue;
else if (cupA==V || cupB==V){
cout << j;
found = true;
break;
}
else{
step[cupA][cupB] = j;

// 4 condition
if (cupA == 0){
// fill cupA
qx.push(X); qy.push(cupB);

// pour cupB to cupA
if (cupB > X){
qx.push(X); qy.push(cupB - X);
}
else{
qx.push(cupB); qy.push(0);
}
}
else if (cupB == 0){
// fill cupB
qx.push(cupA); qy.push(Y);

// pour cupA to cupB
if (cupA > Y){
qx.push(cupA - Y); qy.push(Y);
}
else{
qx.push(0); qy.push(cupA);
}
}
else if (cupA == X){
// empty cupA
qx.push(0); qy.push(cupB);

if (cupA > (Y - cupB)){
qx.push(cupA-(Y-cupB));
qy.push(Y);
}
else{
qx.push(0);qy.push(cupA + cupB);
}
}
else if (cupB == Y){
// empty cupB
qx.push(cupA); qy.push(0);

if (cupB > (X - cupA)){
qx.push(X);
qy.push(cupB-(X-cupA));
}
else{
qx.push(cupA + cupB);qy.push(0);
}
}
}
}
j++;
}

if (!found){
cout << -1;
}

return 0;
}
```

The code may seem long, but most of it are constructing the actions of pouring water. For BFS, the idea is to explore the siblings before their children. So, the code

```#include <queue>
```

which follows the FIFO (first in, first out) rule will make the code simpler. When we have a queue of siblings, their children will be added at the back of the queue and each time we take the first element of the queue to perform pouring actions. So, the siblings will be explored before any of their children.

Now let’s see what the code does. First, we construct a table with `X+1` rows and `Y+1` columns, `step[X+1][Y+1]`. `step[i][j]` is the data for the minimal step to achieve `i` volume of water in the first cup and `j` volume of water in another. Now, where and when should we call the answer? `step[V][2]`? or `step[3][V]`? The good news is, we don’t have to deal with them! Remember that if we use BFS, the first cup that achieved value `V` is the one we seek, because other condition later than that will take more or equal to that number of steps.

Next, we mark every unexplored element as `-1`. Which is all element except `step[0][0]` which is sure to be `0`. This is done in the code:

```int step[X+1][Y+1];
for (int i=0; i<=X; i++){
for (int j=0; j<=Y; j++){
step[i][j] = -1;
}
}
step[0][0] = 0;
step[X][Y] = 0;
```

Next, we construct our `queue`. First, I thought that we can run the BFS algorithm one after another, which takes the other cup as constant. Luckily the mentors pointed out my mistakes, because the cups are not constant and is a big mistake! There are two ways, one is to run BFS for two cups at the same time or use the data type `pair` in but I prefer the first one. Now, we analyse the code piece by piece:

```queue<int> qx;
queue<int> qy;

qx.push(X); qx.push(0);
qy.push(0); qy.push(Y);
```

We have two `queue`s. The first `queue`, `qx` is for the first cup, `cupA` and the second `queue`, `qy` is, of course, for the second cup, `cupB`. Initially, we know the first step must be `(X,0)` and `(0,Y)` so we not need to start from `(0,0)` and write the code for the action needed to perform after it.

```bool found = false;
int j = 1;
while(!qx.empty() && !found){
// some code here
}
```

The boolean `found` is to check if volume `V` is achieved or not and the variable `j` is to record the current step for each condition explored. The condition for `while` loop to iterate is when `qx` is not empty and `V` is not achieved.

```int len = qx.size();
for (int i=0; i<len; i++){
int cupA = qx.front(); qx.pop();
int cupB = qy.front(); qy.pop();

if (step[cupA][cupB] != -1) continue;
else if (cupA==V || cupB==V){
cout << j;
found = true;
break;
}
else{
step[cupA][cupB] = j;

// 4 condition
}
}
j++
```

This is the code in the `while` loop. First, the `for` loop should only run for the size of the current `queue`, this is because every element in the `queue` are now siblings, and should be assigned with the same `j`. After every sibling is explored, `j` is increased by one and the size of `queue` is assigned again. In each `for` loop, `cupA` takes the first value in `qx` and remove it from the `queue`. This works the same for `cupB`. If the value in the table isn’t `-1`, that means that condition hasn’t been explored yet (Remember that we first assigned every element in the table `step` to be `-1`), so we pass to the next `for` loop. If `V` is achieved, we print `j`, break the `for` loop and the boolean `found` can fail the `while` loop. Else, we perform the pouring actions as described in the problem statement, which is the tedious but simplest part.

Finally, if the `while` loops stops because of the empty `queue`, `found` must be false and print `-1`.

P/S: There is another way to seek if `V` is achievable:

```if (V % gcd(X, Y) != 0) // V is not achievable.
```