asteroids.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 224 行

package PKU.BFS;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

/**
 * 
 */

/**
 * ID:2225
 * BFS
 * @author yhm
 *
 */
public class Asteroids {

	
	static int[][] edge = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
	static int size;
	static int[][][] M;
	static boolean Find;
	static AsteroidsNode start;
	static AsteroidsNode end;
	static Queue<AsteroidsNode> Q;
	static int rock = -2;
	static int blank = -1;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			String str = cin.next();
			if(str.equals("START")){
				size = cin.nextInt();
			}
			M = new int[size][size][size];
			Q = new AsteroidsListQueue();
			Find = false;
			for(int l=0;l<size;l++){
				for(int r=0;r<size;r++){
					str = cin.next();
					for(int c=0;c<size;c++){
						M[l][r][c] = str.charAt(c)=='O'?blank:rock;
					}
				}
			}
			int c=cin.nextInt();
			int r=cin.nextInt();
			int l=cin.nextInt();
			start = new AsteroidsNode(l,r,c);
			c=cin.nextInt();
			r=cin.nextInt();
			l=cin.nextInt();
			end = new AsteroidsNode(l,r,c);
			str = cin.next();
			if(str.equals("END")){
				int result =BFS();
				if(result!=-1){
					System.out.println(size+" "+result);
				}
				else{
					System.out.println("NO ROUTE");
				}
				continue;
			}
		}
		

	}
	
	static boolean overflow(int x,int y,int z){
		return (x<0 || y<0 || z<0 ||x>=size || y>=size || z>=size);
	}
	static int BFS(){
		int l = start.l;
		int r = start.r;
		int c = start.c;
		M[l][r][c] = 0;
		if(start.equals(end)){
			Find=true;
			return M[l][r][c];
		}
		Q.offer(new AsteroidsNode(l,r,c));
		
		while(!Q.isEmpty()){
			AsteroidsNode current = Q.poll();
			for(int i=0;i<6;i++){
				l = current.l+edge[i][0];
				r = current.r+edge[i][1];
				c = current.c+edge[i][2];
				if(overflow(l,r,c)){
					continue;
				}
				if(M[l][r][c]==blank){
					M[l][r][c] = M[current.l][current.r][current.c]+1;
					AsteroidsNode n = new AsteroidsNode(l,r,c);
					Q.offer(n);
					if(n.equals(end)){
						return M[l][r][c];
					}
				}
			}
		}
		return -1;
	}

}

class AsteroidsNode{
	int l;
	int r;
	int c;
	public AsteroidsNode(int l, int r, int c) {
		super();
		this.l = l;
		this.r = r;
		this.c = c;
	}
	public boolean equals(AsteroidsNode n){
		return (l==n.l && r==n.r && c==n.c);
	}
	
}


class AsteroidsListQueue implements Queue{

	private List l = new LinkedList();
	public Object element() {
		// TODO Auto-generated method stub
		return null;
	}

	public boolean offer(Object o) {
		return l.add(o);
	}

	public Object peek() {
		// TODO Auto-generated method stub
		return null;
	}

	public Object poll() {
		// TODO Auto-generated method stub
		return l.remove(0);
	}

	public Object remove() {
		// TODO Auto-generated method stub
		return null;
	}

	public boolean add(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean addAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}

	public void clear() {
		// TODO Auto-generated method stub
		
	}

	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean containsAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return l.isEmpty();
	}

	public Iterator iterator() {
		// TODO Auto-generated method stub
		return null;
	}

	public boolean remove(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean removeAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean retainAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}

	public int size() {
		// TODO Auto-generated method stub
		return 0;
	}

	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}

	public Object[] toArray(Object[] a) {
		// TODO Auto-generated method stub
		return null;
	}
	
}