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 queues. 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.
Advertisements
UOJ CUP : Breadth First Search (BFS)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s