primepath.java

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

package PKU.BFS;
import java.util.*;


/**
 * ID:3126
 * BFS
 * @author yhm
 *
 */
public class PrimePath {

	static int start;
	static int end;
	static Queue<Integer> Q;
	static int[] M;
	static boolean Find;
	/**
	 * @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++){
			start = cin.nextInt();
			end = cin.nextInt();
			Q = new PrimePathListQueue();
			M = new int[10000];
			Arrays.fill(M, -1);
			Find = false;
			BFS();
			if(Find){
				System.out.println(M[end]);
			}
			else{
				System.out.println("Impossible");
			}
		}

	}
	
	static boolean isPrime(int x){
		int y = (int)Math.ceil(Math.sqrt(x));
		for(int i=2;i<=y;i++){
			if(x%i==0){
				return false;
			}
		}
		return true;
	}

	static void BFS(){
		M[start] = 0;
		Q.offer(start);
		if(start==end){
			Find = true;
			return;
		}
		while(!Q.isEmpty()){
			int current = Q.poll();
			for(int i=0;i<4;i++){
				if(i==0){
					for(int j=1;j<=9;j++){
						StringBuffer str = new StringBuffer(""+current);
						String newStr = str.replace(i, i+1, ""+j).toString();
						int newInt = Integer.parseInt(newStr);
						if(M[newInt]==-1 && isPrime(newInt)){
							M[newInt] = M[current]+1;
							Q.offer(newInt);
							if(newInt==end){
								Find = true;
								return;
							}
						}
					}
				}
				else{
					for(int j=0;j<=9;j++){
						StringBuffer str = new StringBuffer(""+current);
						String newStr = str.replace(i, i+1, ""+j).toString();
						int newInt = Integer.parseInt(newStr);
						if(M[newInt]==-1 && isPrime(newInt)){
							M[newInt] = M[current]+1;
							Q.offer(newInt);
							if(newInt==end){
								Find = true;
								return;
							}
						}
					}
				}
			}
		}
	}

}


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