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写队列的童鞋伤不起啊!附上RZ的代码!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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator