catchthatcow.java

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

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


/**
 * ID:3278
 * BFS
 * @author yhm
 *
 */
public class CatchThatCow {

	static int MAX = 200001;
	static Queue<Integer> Q;
	static int start;
	static int end;
	static int[] visit;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		start = cin.nextInt();
		end = cin.nextInt();
		visit = new int[MAX];
		Q = new CatchTahatCowListQueue();
		Arrays.fill(visit, -1);
		if(start>=end){
			System.out.println(start-end);
		}
		else{
			BFS();	
		}
		
		


	}
	
	static boolean overflow(int x){
		return (x<0 || x>=MAX);
	}
	static void BFS(){
		visit[start] = 0;
		Q.offer(new Integer(start));
		
		while(!Q.isEmpty()){
			int current = Q.poll();
			for(int i=0;i<3;i++){
				int newX = 0;
				if(i==0){
					newX = current+1;
				}
				else if(i==1){
					newX = current-1;
				}
				else{
					newX = 2*current;
				}
				
				if(!overflow(newX) && visit[newX]==-1){
					visit[newX] = visit[current]+1;
					Q.offer(new Integer(newX));
					if(newX==end){
						System.out.println(visit[newX]);
						return;
					}
				}
			}
		}
	}
	

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