dungeonmaster.java

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

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:2251
 * BFS
 * @author yhm
 *
 */
public class DungeonMaster {

	static int rock = -2;
	static int blank = -1;
	static int start = 0;
	static int end = -1;
	
	
	static int L;
	static int R;
	static int C;
	static int[][][] D;
	
	static int startL=0,startR=0,startC=0;
	static int endL=0,endR=0,endC=0;
	
	
	static Point[] edge = new Point[6];
	
	
	static Queue<Point> Q;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		edge[0] = new Point(0,1,0);
		edge[1] = new Point(0,-1,0);
		edge[2] = new Point(0,0,1);
		edge[3] = new Point(0,0,-1);
		edge[4] = new Point(1,0,0);
		edge[5] = new Point(-1,0,0);

		
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			L = cin.nextInt();
			R = cin.nextInt();
			C = cin.nextInt();
			if(L==0&&R==0&&C==0){
				break;
			}
			
			D = new int[L][R][C];
			Q = new ListQueue();
			for(int l=0;l<L;l++){
				for(int r=0;r<R;r++){
					String str = cin.next();
					for(int c=0;c<C;c++){
						if(str.charAt(c)=='.'){
							D[l][r][c] = blank;
						}
						else if(str.charAt(c)=='S'){
							D[l][r][c] = start;
							startL = l;
							startR = r;
							startC = c;
						}
						else if(str.charAt(c)=='E'){
							D[l][r][c] = end;
							endL = l;
							endR = r;
							endC = c;
						}
						else{
							D[l][r][c] = rock;
						}
						
					}
				}
			}
			
			
			int r = BFS(startL, startR, startC);
			if(r==-1){
				System.out.println("Trapped!");
			}
			else{
				System.out.println("Escaped in "+r+" minute(s).");
			}
			
			
		}

	}
	
	
	static boolean overflow(int l, int r, int c){
		if(l<0 || l>=L){
			return true;
		}
		if(r<0 || r>=R){
			return true;
		}
		if(c<0 || c>=C){
			return true;
		}
		return false;
	}
	
	static int BFS(int l, int r, int c){
		int mark=0;
		D[l][r][c] = mark;
		Q.offer(new Point(l,r,c));
		while(!Q.isEmpty()){
			Point p = Q.poll();
			for(int i=0;i<6;i++){
				int l1 = p.l + edge[i].l;
				int r1 = p.r + edge[i].r;
				int c1 = p.c + edge[i].c;
				
				if(overflow(l1,r1,c1)){
					continue;
				}
				
				if(D[l1][r1][c1]==blank){
					mark = D[p.l][p.r][p.c]+1;
					D[l1][r1][c1] = mark;
					if(l1==endL && r1==endR && c1==endC){
						return mark;
					}
					Q.offer(new Point(l1,r1,c1));
				}
			}
		}
		
		return -1;
		
	}
	

	
	

	
}














class Point{
	int l;
	int r;
	int c;
	public Point(int l, int r, int c) {
		super();
		this.l = l;
		this.r = r;
		this.c = c;
	}
}




class ListQueue 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;
	}
	
}