$$\color{Red}{抓住那头牛——BFS最短路}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

农夫知道一头牛的位置，想要抓住它。

农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。

农夫有两种移动方式：

从 X 移动到 X−1 或 X+1，每次移动花费一分钟
从 X 移动到 2∗X，每次移动花费一分钟假设牛没有意识到农夫的行动，站在原地不动。

农夫最少要花多少时间才能抓住牛？
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

数据保证至少存在一条从左上角走到右下角的路径。

输入格式

共一行，包含两个整数N和K。

输出格式

输出一个整数，表示抓到牛所花费的最少时间
。
数据范围

0 ≤ N, K ≤ 10 ^ 5

输入样例：

5 17

输出样例：

4

思路

BFS为基础，需要初始化距离为-1来避免重搜，那么-1的范围，应该是大于等于0，0可能是答案，其次缩小乘2可能也是答案。+1的范围应该是小于等于end。最后乘2的范围应该是end + 1，因为可能答案是乘2后再减1如果从牛最大可能在的地方再乘2，就必须往回走了。而且如果先往回走再乘2，一定更优。因为如果那样的话，就相当于一次性走了两步。所以，一定不会大于牛最大可能在的地方再加1的位置。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 100010, start, end;
    static int[] d = new int[N];
    static int[] q = new int[N];

    public static void bfs(int x) {
        int hh = 0, tt = 0;
        q[hh] = x;
        d[x] = 0;
        while (hh <= tt) {
            int t = q[hh++];
            if (t == end){
                System.out.println(d[t]);
                break;
            }
            if (t - 1 >= 0 && d[t - 1] == -1){
                q[++tt] = t - 1;
                d[t - 1] = d[t] + 1;
            }
            if (t + 1 <= end && d[t + 1] == -1){
                q[++tt] = t + 1;
                d[t + 1] = d[t] + 1;
            }
            if (2 * t <= end + 1 && d[2 * t] == -1) {
                q[++tt] = 2 * t;
                d[2 * t] = d[t] + 1;
            }
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        Arrays.fill(d, -1);
        start = Integer.parseInt(s1[0]);
        end = Integer.parseInt(s1[1]);
        bfs(start);
    }
}