题目描述
blablabla
每一次可以选择其中任意一种的方向移动
1.范围的确定,宽泛的说是2e5,但是实际上1e5也是成立的。
2.不能走重复路线,因为需要耗费一定的时间,向前走一步在折回来相当于没走;或者说向前跨越两倍的距离后,在折回来一一半,是和一步一步向前走的距离一样的
代码
package bfs;
import java.io.IOException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*
* 1.范围的确定,宽泛的说是2e5,但是实际上1e5也是成立的。
* 2.不能走重复路线,因为需要耗费一定的时间,向前走一步在折回来相当于没走;或者说向前跨越两倍的距离后,在折回来一一半,是和一步一步向前走的距离一样的
* */
public class 抓住那头牛 {
public static int N=(int) 1e5,M=(int) 1e5,k;
public static int path[]=new int [N];
public static int bfs (int n) {
//if(n==k) return path[k];
Queue<Integer> queue =new LinkedList<Integer>();
queue.add(n);
path[n]=0;
while(!queue.isEmpty()){
int t=queue.poll();
//System.out.println(t+" "+path[t]);
if(t+1<=M && path[t+1]==-1){
queue.add(t+1);
path[t+1]=1+path[t];
//System.out.println((1+t)+" "+path[t+1]);
if(t+1==k) return path[t+1];
}
if(t-1>=0 && path[t-1]==-1) {
queue.add(t-1);
path[t-1]=1+path[t];
//System.out.println((t-1)+" "+path[t-1]);
if(t-1==k) return path[t-1];
}
if(t*2 <=M && path[t*2]==-1) {
queue.add(2*t);
path[t*2]=1+path[t];
//System.out.println((2*t)+" "+path[t*2]);
if(t*2==k) return path[t*2];
}
}
return 0;
}
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
k=scanner.nextInt();
Arrays.fill(path, -1);
System.out.println(bfs(n));
}
}