首页 > 专题系列 > Java解POJ > POJ 3414 Pots [解题报告] Java
2013
11-12

POJ 3414 Pots [解题报告] Java

Pots

问题描述 :

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

  1. FILL(i)        fill the pot i (1 ≤ i ≤ 2) from the tap;
  2. DROP(i)      empty the pot i to the drain;
  3. POUR(i,j)    pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

输入:

On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

输出:

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

样例输入:

3 5 4

样例输出:

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

解题代码:

//* @author:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main{
 private static final String[] status = new String[] { "", "FILL(1)",
	"FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)" };
 private static boolean[][] visted = new boolean[101][101];
 private static int a;
 private static int b;
 private static int c;

 public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	for (int i = 0; i < 101; ++i) {
		for (int j = 0; j < 101; ++j)
			visted[i][j] = false;
	}
	a = sc.nextInt();
	b = sc.nextInt();
	c = sc.nextInt();
	bfs();
  }

  static void bfs() {
	boolean is = false;
	LinkedList< Node> queue = new LinkedList< Node>();
	Node p = new Node();
	p.aa = 0;
	p.bb = 0;
	visted[p.aa][p.bb] = true;
	queue.addLast(p);
	// visted[p.aa][p.bb] = true;
	// p = new Node();
	// p.aa = 0;
	// p.bb = b;
	// p.status.add(2);
	// visted[p.aa][p.bb] = true;
	// queue.addLast(p);
	while (!queue.isEmpty()) {
	 Node front = queue.getFirst();
	 queue.remove();
	 int r = -1;
	 for (int i = 1; i <= 6; ++i) {
	  int aa = front.aa;
	  int bb = front.bb;
	  int flag = i;
	  switch (flag) {
	   case 1:
		aa = a;
		break;
	   case 2:
		bb = b;
		break;
	   case 3:
		aa = 0;
		break;
	   case 4:
		bb = 0;
		break;
	   case 5:
		r = b - bb;
		bb = bb + (r <= aa ? r : aa);
		aa = (r <= aa ? (aa - r) : 0);
		break;
	   case 6:
		r = a - aa;
		aa = aa + (r <= bb ? r : bb);
		bb = (r <= bb ? (bb - r) : 0);
		break;
	   default:
		break;
	   }
	   if (aa == c || bb == c) {
		int size = front.status.size();
		System.out.println(size + 1);
		for (int j = 0; j < size; ++j)
	         System.out.println(status[front.status.get(j)]);
		System.out.println(status[flag]);
		is = true;
		return;
	    }
	    if (!visted[aa][bb]) {
		 Node tmp = new Node();
		 tmp.aa = aa;
		 tmp.bb = bb;
		 int size = front.status.size();
		 for (int j = 0; j < size; ++j)
		    tmp.status.add(front.status.get(j));
		 tmp.status.add(flag);
		 visted[aa][bb] = true;
		 queue.addLast(tmp);
	     }
	 }
	}
	if (!is)
	  System.out.println("impossible");
 }

 private static class Node {
	private int aa;
	private int bb;
	private ArrayList< Integer> status = new ArrayList< Integer>();
 }
}

  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.