src.rar_ Binary search java_KMP_PKU_java pku_并查集算法

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; } }*/