pots.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 281 行

package PKU.BFS;

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;



/**
 * ID:3414
 * BFS
 * @author yhm
 *
 */
public class Pots {

	static int A=0;
	static int B=0;
	static int C=0;
	
	static int mark = -1;
	static int blank = 0;
	
	static Queue<Node> Q;
	static Node[][] pot;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		A = cin.nextInt();
		B = cin.nextInt();
		C = cin.nextInt();
		pot = new Node[A+1][B+1];
		Q = new ListQueue();
		BFS();

	}
	
	
	static void BFS(){
		Node root = new Node(0,0,null,0);
		pot[0][0] = root;
		Q.offer(root);
		while(!Q.isEmpty()){
			Node n = Q.poll();
			for(int i=1;i<=6;i++){
				Node next = findNextNode(n, i);
				int l1 = next.l1;
				int l2 = next.l2;
				if(pot[l1][l2]==null){
					pot[l1][l2] = next;
					if(l1==C || l2==C){
						//do something
						StringBuffer str = new StringBuffer();
						Node node = next;
						int num=0;
						while(node.prev!=null){
							num++;
							str.insert(0, translate(node.mark));
							node = node.prev;							
						}
						str.insert(0, num+"\n");
						System.out.println(str.toString());
						return;
					}
					Q.offer(next);
				}
			}
		}
		
		System.out.println("impossible");
		
	}
	
	static String translate(int edge){
		if(edge==1){
			//FILL(1)
			return "FILL(1)\n";
		}
		else if(edge==2){
			//FILL(2)
			return "FILL(2)\n";

		}
		else if(edge==3){
			//DROP(1)
			return "DROP(1)\n";

		}
		else if(edge==4){
			//DROP(2)
			return "DROP(2)\n";

		}
		else if(edge==5){
			//POUR(1,2)
			return "POUR(1,2)\n";

		}
		else{
			//POUR(2,1)
			return "POUR(2,1)\n";

		}
	}
	
	static Node findNextNode(Node current, int edge){
		Node n = null;
		int l1=0;
		int l2=0;
		if(edge==1){
			//FILL(1)
			l1 = A;
			l2 = current.l2;
			n = new Node(l1,l2,current,edge);
			
		}
		else if(edge==2){
			//FILL(2)
			l1 = current.l1;
			l2 = B;
			n = new Node(l1,l2,current,edge);
		}
		else if(edge==3){
			//DROP(1)
			l1 = 0;
			l2 = current.l2;
			n = new Node(l1,l2,current,edge);
		}
		else if(edge==4){
			//DROP(2)
			l1 = current.l1;
			l2 = 0;
			n = new Node(l1,l2,current,edge);
		}
		else if(edge==5){
			//POUR(1,2)
			if(current.l1+current.l2>B){
				l2 = B;
				l1 = current.l1-(B-current.l2);
			}
			else{
				l2 = current.l2+current.l1;
				l1 = 0;
			}
			n = new Node(l1,l2,current,edge);
		}
		else{
			//POUR(2,1)
			if(current.l1+current.l2>A){
				l1 =  A;
				l2 = current.l2-(A-current.l1);
			}
			else{
				l1 = current.l1+current.l2;
				l2 = 0;
			}
			n = new Node(l1,l2,current,edge);
		}
		return n;
		
	}

}


class Node{
	int l1;
	int l2;
	Node prev;
	int mark;
	public Node(int l1, int l2, Node prev,int mark) {
		super();
		this.l1 = l1;
		this.l2 = l2;
		this.prev = prev;
		this.mark = mark;
	}
}




/*
class ListQueue implements Queue{

	private List l = new LinkedList();
	public Object element() {
		// TODO Auto-generated method stub
		return null;
	}

	public boolean offer(Object o) {
		return l.add(o);
	}

	public Object peek() {
		// TODO Auto-generated method stub
		return null;
	}

	public Object poll() {
		// TODO Auto-generated method stub
		return l.remove(0);
	}

	public Object remove() {
		// TODO Auto-generated method stub
		return null;
	}

	public boolean add(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean addAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}

	public void clear() {
		// TODO Auto-generated method stub
		
	}

	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean containsAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return l.isEmpty();
	}

	public Iterator iterator() {
		// TODO Auto-generated method stub
		return null;
	}

	public boolean remove(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean removeAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean retainAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}

	public int size() {
		// TODO Auto-generated method stub
		return 0;
	}

	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}

	public Object[] toArray(Object[] a) {
		// TODO Auto-generated method stub
		return null;
	}
	
}*/