HDU2717-Catch That Cow

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

import java.util.*;
public class Main {
	public LinkedList<Node> queue;
	public boolean []visit;
	public Main(){
		this.queue=new LinkedList<Main.Node>();
		visit=new boolean[200000];
	}
	public class Node{
		int num;
		int count;
		public Node(){}
		public Node(int num,int count) {
			this.num=num;
			this.count=count;
		}
	}
	public int bfs(int n,int k){
		if(n==k) return 0; 
		Node n0=new Node(n,0);
		
		queue.add(n0);
		visit[n]=true;
		
		while(!queue.isEmpty()){
			Node tmp=queue.peek();
			if(tmp.num==k) return tmp.count; 
			queue.remove();
			Node n1=new Node(tmp.num-1,tmp.count+1);
			Node n2=new Node(tmp.num+1,tmp.count+1);
			Node n3=new Node(tmp.num*2,tmp.count+1);
			if(n1.num==k) return n1.count;
			if(n2.num==k) return n2.count; 
			if(n3.num==k) return n3.count; 
			if(n1.num<150005 && n1.num>=0 && visit[n1.num]!=true ){
				queue.add(n1);
				visit[n1.num]=true;
			}
			if(n2.num<150005 && n2.num>=0 && visit[n2.num]!=true) {
				queue.add(n2);
				visit[n2.num]=true;
			}
			if(n3.num<150005 && n3.num>=0 && visit[n3.num]!=true){
				queue.add(n3);
				visit[n3.num]=true;
			}
		}
		return 0;
	}
	public static void main(String[] args) {
		int n,k;
		Scanner cin=new Scanner(System.in);
		while(cin.hasNext()){
			n=cin.nextInt();
			k=cin.nextInt();
			System.out.println(new Main().bfs(n, k));
		}
	}

}

HDU2717-Catch That Cow,布布扣,bubuko.com

HDU2717-Catch That Cow

原文：http://blog.csdn.net/dutsoft/article/details/27663821