2016HUAS暑假集训训练题 B

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