(UVA) Jugs - Solution
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=646&page=show_problem&problem=512
The solution below used Breadth-First Search (BFS) to solve this problem.
We can use this algorithm because the structure resultant of the operations is like a tree, and a tree is a graph. Then, we can apply graph algorithms to solve it.
import java.io.*;
import java.util.*;
class Main {
public int capacityA;
public int capacityB;
public int target;
public ArrayList<String> operations;
public void bfs(int startA, int startB) {
Queue<Jug> queue = new ArrayDeque<>();
queue.add(new Jug(startA, startB, "", -1, -1));
Jug[][] visited = new Jug[capacityA+1][capacityB+1];
while (queue.size() > 0) {
Jug curr = queue.poll();
int currA = curr.a;
int currB = curr.b;
String currOp = curr.op;
int currPreviousA = curr.previousA;
int currPreviousB = curr.previousB;
if (visited[currA][currB] != null) {
continue;
}
visited[currA][currB] = curr;
if (currB == target) {
int cA = currA;
int cB = currB;
while (cA != 0 || cB != 0) { // until it reaches the initial state
operations.add(visited[cA][cB].op);
int tmpCA = visited[cA][cB].previousA;
cB = visited[cA][cB].previousB;
cA = tmpCA;
}
return;
}
queue.add(new Jug(capacityA, currB, "fill A", currA, currB)); // fill A
queue.add(new Jug(currA, capacityB, "fill B", currA, currB)); // fill B
queue.add(new Jug(0, currB, "empty A", currA, currB)); // empty A
queue.add(new Jug(currA, 0, "empty B", currA, currB)); // empty B
int capacityDest = capacityB-currB;
int pour = Math.min(currA, capacityDest);
queue.add(new Jug(currA-pour, currB+pour, "pour A B", currA, currB)); // pour A B
capacityDest = capacityA-currA;
pour = Math.min(currB, capacityDest);
queue.add(new Jug(currA+pour, currB-pour, "pour B A", currA, currB)); // pour B A
}
}
public void process() throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while (sc.hasNext()) {
capacityA = sc.nextInt();
capacityB = sc.nextInt();
target = sc.nextInt();
operations = new ArrayList<>();
bfs(0, 0);
for (int i = operations.size()-1; i >= 0; i--) {
bw.write(operations.get(i)+"\n");
}
bw.write("success\n");
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
class Jug {
int a;
int b;
String op;
int previousA;
int previousB;
public Jug(int a, int b, String op, int previousA, int previousB) {
this.a = a;
this.b = b;
this.op = op;
this.previousA = previousA;
this.previousB = previousB;
}
}
The solution below used Breadth-First Search (BFS) to solve this problem.
We can use this algorithm because the structure resultant of the operations is like a tree, and a tree is a graph. Then, we can apply graph algorithms to solve it.
import java.io.*;
import java.util.*;
class Main {
public int capacityA;
public int capacityB;
public int target;
public ArrayList<String> operations;
public void bfs(int startA, int startB) {
Queue<Jug> queue = new ArrayDeque<>();
queue.add(new Jug(startA, startB, "", -1, -1));
Jug[][] visited = new Jug[capacityA+1][capacityB+1];
while (queue.size() > 0) {
Jug curr = queue.poll();
int currA = curr.a;
int currB = curr.b;
String currOp = curr.op;
int currPreviousA = curr.previousA;
int currPreviousB = curr.previousB;
if (visited[currA][currB] != null) {
continue;
}
visited[currA][currB] = curr;
if (currB == target) {
int cA = currA;
int cB = currB;
while (cA != 0 || cB != 0) { // until it reaches the initial state
operations.add(visited[cA][cB].op);
int tmpCA = visited[cA][cB].previousA;
cB = visited[cA][cB].previousB;
cA = tmpCA;
}
return;
}
queue.add(new Jug(capacityA, currB, "fill A", currA, currB)); // fill A
queue.add(new Jug(currA, capacityB, "fill B", currA, currB)); // fill B
queue.add(new Jug(0, currB, "empty A", currA, currB)); // empty A
queue.add(new Jug(currA, 0, "empty B", currA, currB)); // empty B
int capacityDest = capacityB-currB;
int pour = Math.min(currA, capacityDest);
queue.add(new Jug(currA-pour, currB+pour, "pour A B", currA, currB)); // pour A B
capacityDest = capacityA-currA;
pour = Math.min(currB, capacityDest);
queue.add(new Jug(currA+pour, currB-pour, "pour B A", currA, currB)); // pour B A
}
}
public void process() throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while (sc.hasNext()) {
capacityA = sc.nextInt();
capacityB = sc.nextInt();
target = sc.nextInt();
operations = new ArrayList<>();
bfs(0, 0);
for (int i = operations.size()-1; i >= 0; i--) {
bw.write(operations.get(i)+"\n");
}
bw.write("success\n");
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
class Jug {
int a;
int b;
String op;
int previousA;
int previousB;
public Jug(int a, int b, String op, int previousA, int previousB) {
this.a = a;
this.b = b;
this.op = op;
this.previousA = previousA;
this.previousB = previousB;
}
}
Comments
Post a Comment