| ||||||||||
| 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