knightmoves.java

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

package PKU.BFS;

import java.util.*;






/**
 * ID:1915
 * BFS
 * @author yhm
 *
 */
public class KnightMoves {

	static int[][] board;
	static int size;
	static KnightMovesPoint begin;
	static KnightMovesPoint end;
	static Queue<KnightMovesPoint> Q;
	
	static int[] xEdge = {1,2,2,1,-1,-2,-2,-1};
	static int[] yEdge = {2,1,-1,-2,-2,-1,1,2};
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		for(int i=0;i<caseNum;i++){
			size = cin.nextInt();
			board = new int[size][size];
			Q = new KnightMovesListQueue();
			for(int j=0;j<size;j++){
				Arrays.fill(board[j], -1);
			}
			begin = new KnightMovesPoint(cin.nextInt(),cin.nextInt());
			end = new KnightMovesPoint(cin.nextInt(),cin.nextInt());
			
			int r = BFS();
			System.out.println(r);
			
		}

	}
	
	static boolean overflow(int x, int y){
		return (x<0 || y<0 || x>=size || y>=size);
	}
	
	static int BFS(){
		int x = begin.x;
		int y = begin.y;
		board[x][y] = 0;
		Q.offer(begin);

		if(begin.equals(end)){
			return board[x][y];
		}
		
		while(!Q.isEmpty()){
			KnightMovesPoint current = Q.poll();
			for(int i=0;i<8;i++){
				x = current.x + xEdge[i];
				y = current.y + yEdge[i];
				if(!overflow(x,y)){
					if(board[x][y]==-1){
						board[x][y] = board[current.x][current.y]+1;
						KnightMovesPoint newPoint = new KnightMovesPoint(x,y);
						if(newPoint.equals(end)){
							return board[x][y];
						}
						Q.offer(newPoint);
					}
				}
			}
		}
		return -1;
		
	}
	


}


class KnightMovesPoint{
	int x;
	int y;
	public KnightMovesPoint(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	
	public boolean equals(KnightMovesPoint p){
		return (x==p.x && y == p.y);
	}
	
}






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