首页 > 代码库 > HDU2717-Catch That Cow

HDU2717-Catch That Cow

2024-07-06 15:39:33   221人阅读

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

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));
		}
	}

}



联系
我们