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写队列的童鞋伤不起啊!附上RZ的代码!

Posted by 6756100 at 2011-07-10 01:59:58 on Problem 3414
import java.util.Scanner;

public class Main {

	static boolean visited[][] = new boolean[101][101];
	static String[] str = { "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)","POUR(1,2)", "POUR(2,1)" };
	static int step;
	static class Node {
		Node pre;
		int a;
		int b;
		int coperation;
		public Node() {
		}
	}

	static class Queue {
		Node[] nodes;
		int front, rear, size;

		public Queue(int n) {
			front = rear = 0;
			size = 0;
			nodes = new Node[n];
		}

		public void append(Node node) {
			nodes[rear] = node;
			rear++;
			size++;
		}

		public Node delete() {
			Node temp = nodes[front];
			front = front + 1;
			size --;
			return temp;
		}

		public boolean isEmpty() {
			return size == 0;
		}
	}
	
	public static void print(Node node) {
		if(node.pre != null) {
			step ++;
			print(node.pre);
			System.out.println(str[node.coperation]);
		}
	}
	
	public static void cout(Node node) {
		if(node.pre != null) {
			step ++;
			cout(node.pre);
		}
	}

	public static int min(int a, int b) {
		return (a < b) ? a : b;
	}

	public static void bfs(int a, int b, int c, Queue q) {
		step = 0;
		Node temp = new Node();
		temp.a = temp.b = 0;
		temp.pre = null;
		q.append(temp);
		while (!q.isEmpty()) {
			Node node = q.delete();
			if (node.a == c || node.b == c) {
				cout(node);
				System.out.println(step);
				print(node);
				return;
			}
			if (!visited[a][node.b]) {
				Node n = new Node();
				n.a = a;
				n.b = node.b;
				n.pre = node;
				n.coperation = 0;
				visited[a][node.b] = true;
				q.append(n);
			}
			if (!visited[node.a][b]) {
				Node n = new Node();
				n.a = node.a;
				n.b = b;
				n.pre = node;
				n.coperation = 1;
				visited[node.a][b] = true;
				q.append(n);
			}
			if (!visited[0][node.b]) {
				Node n = new Node();
				n.a = 0;
				n.b = node.b;
				n.pre = node;
				n.coperation = 2;
				visited[0][node.b] = true;
				q.append(n);
			}
			if (!visited[node.a][0]) {
				Node n = new Node();
				n.coperation = 3;
				n.a = node.a;
				n.b = 0;
				n.pre = node;
				visited[node.a][0] = true;
				q.append(n);
			}
			int min = min(node.a,b - node.b);
			if(!visited[node.a-min][node.b+min]) {
				Node n = new Node();
				n.coperation = 4;
				n.a = node.a - min;
				n.b = node.b + min;
				n.pre = node;
				visited[node.a - min][node.b + min] = true;
				q.append(n);
			}
			int min1 = min(a-node.a,node.b);
			if(!visited[node.a + min1][node.b - min1]) {
				Node n = new Node();
				n.coperation = 5;
				n.a = node.a + min1;
				n.b = node.b - min1;
				n.pre = node;
				visited[node.a + min1][node.b - min1] = true;
				q.append(n);
			}
		}
		System.out.println("impossible");
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int m = scan.nextInt();
		int n = scan.nextInt();
		int p = scan.nextInt();
		Queue q = new Queue(101*101);
		bfs(m,n,p,q);
	}

}

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