Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Java 1000MS飘过

Posted by 18718371621 at 2019-02-16 11:44:37 on Problem 3414
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator