//注意,需要特判n是否大于k,大于k时只能向左,输出n-k。第一次提交没注意,结果RE了,,
Catch That Cow
Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 137789
Accepted: 42551
Description
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?
Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
Source
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Point{
public int x;
public int count;
public Point(int x,int y){
this.x=x;
this.count=y;
}
public Point(){}
}
public class Main{
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int k=in.nextInt();
boolean vis[]=new boolean[k*2];
if(n>=k)System.out.println(n-k);
else
System.out.println(bfs(n,k,vis));
}
private static int bfs(int xx, int k,boolean vis[]) {
Queue<Point> q=new LinkedList<Point>();
Point p=new Point();
p.x=xx;
p.count=0;
vis[p.x]=true;
q.add(p);
while(!q.isEmpty()){
Point n=q.remove();
if(n.x>=2*k||n.x<0)continue;
if(n.x==k){
return n.count;
}else{
for(int i=0;i<3;i++)
{
Point n1=new Point();
if(i==0){
n1.x=n.x+1;
}
else if(i==1)
n1.x=n.x-1;
else
n1.x=2*n.x;
if((!(n1.x>=2*k||n1.x<0))&&vis[n1.x]==false)
{
vis[n1.x]=true;
n1.count=n.count+1;
q.add(n1);
}
}
}
}
return 0;
}
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章