Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Java 1000MS飘过import java.util.ArrayDeque; import java.util.Arrays; import java.util.Queue; import java.util.Scanner; class Node{ int a,b; StringBuilder sb = new StringBuilder(); public Node(int a, int b, String str) { this.a = a; this.b = b; sb.append(str); } } public class Main { static String path[] = { "FILL(1)" ,"FILL(2)" ,"DROP(1)" ,"DROP(2)" ,"POUR(1,2)" ,"POUR(2,1)" }; static boolean [][]flag = new boolean [101][101]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); Queue<Node> que = new ArrayDeque<Node>(); que.add(new Node(0, 0, "")); flag[0][0] = true; Node t = new Node(0, 0, null); while(!que.isEmpty()){ t = que.poll(); if(t.a==c || t.b==c){ System.out.println(t.sb.length()); for(int i=0; i<t.sb.length(); i++) System.out.println(path[t.sb.charAt(i)-'0']); System.exit(0); } if(t.a<a && flag[a][t.b]==false){ flag[a][t.b]=true; que.add(new Node(a, t.b, t.sb.toString()+'0')); } if(t.b<b && flag[t.a][b]==false){ flag[t.a][b]=true; que.add(new Node(t.a, b, t.sb.toString()+'1')); } if(t.a!=0 && flag[0][t.b]==false){ flag[0][t.b]=true; que.add(new Node(0, t.b, t.sb.toString()+'2')); } if(t.b!=0 && flag[t.a][0]==false){ flag[t.a][0]=true; que.add(new Node(t.a, 0, t.sb.toString()+'3')); } if(t.b<b){ if(t.a>=(b-t.b) && flag[t.a-(b-t.b)][b]==false){ flag[t.a-(b-t.b)][b]=true; que.add(new Node(t.a-(b-t.b), b, t.sb.toString()+'4')); }else{ if(t.a+t.b>b) continue; if(flag[0][t.a+t.b]==false){ flag[0][t.a+t.b]=true; que.add(new Node(0, t.a+t.b, t.sb.toString()+'4')); } } } if(t.a<a){ if(t.b>=(a-t.a) && flag[a][t.b-(a-t.a)]==false){ flag[a][t.b-(a-t.a)]=true; que.add(new Node(a, t.b-(a-t.a), t.sb.toString()+'5')); }else{ if(t.a+t.b>a) continue; if(flag[t.a+t.b][0]==false){ flag[t.a+t.b][0]=true; que.add(new Node(t.a+t.b,0, t.sb.toString()+'5')); } } } } System.out.println("impossible"); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator