Catch That Cow

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

最后

以上就是凶狠香菇为你收集整理的Catch That Cow的全部内容，希望文章能够帮你解决Catch That Cow所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。