B - Catch That Cow
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.
本题大概意思是John想要抓一头牛，告诉你john的位置和牛的位置 john有三种移动方式，分别为+1，-1，*2 求抓到牛的最小步数；本题考虑用bfs搜索
依次把得到的数存入计数数组得到到达它所需的步数 再一个一个找直到找到牛就是最小步数
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(new BufferedInputStream(System.in));
while (s.hasNext()) {
int a = s.nextInt(), b = s.nextInt();
int[] l = new int[100010];
int starts = 0;
int ends = 0;
l[0] = a;
int n[] = new int[100010];
Arrays.fill(n, 0);
while (true) {
int v = l[starts];
if (v == b)
break;
if (n[v+ 1] == 0 && v + 1 <= 100000) {
l[++ends] = v + 1;
n[v + 1] = n[v] + 1;
}
if (v - 1 >= 0 && n[v - 1] == 0) {
l[++ends] = v - 1;
n[v - 1] = n[v] + 1;
}
if (v * 2 <= 100000 && n[v * 2] == 0) {
l[++ends] = v * 2;
n[v * 2] = n[v] + 1;
}
starts++;
}
System.out.println(n[b]);
}
s.close();
}
}