acwing1100. 抓住那头牛（最短路模型bfs）

农夫知道一头牛的位置，想要抓住它。
农夫和牛都位于数轴上，农夫起始位于点 NN，牛位于点 KK。
农夫有两种移动方式：

1. 从 XX 移动到 X−1X−1 或 X+1X+1，每次移动花费一分钟
2. 从 XX 移动到 2∗X2∗X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。
农夫最少要花多少时间才能抓住牛？

输入格式

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

输出格式

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

数据范围

0≤N,K≤1050≤N,K≤105

输入样例：

5 17

输出样例：

4

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int dist[N];
int q[N];
int n,k;
int bfs() {
    int hh = 0, tt = 0;
    q[0] = n;
    memset(dist,-1,sizeof dist);
    dist[n] = 0;
    while (hh <= tt) {
        int t = q[hh++];
        if (t == k) return dist[t];
        if (t + 1 < N && dist[t+1] == -1) {
            dist[t+1] = dist[t]+1;
            q[++tt] = t + 1;
        }
        if (t * 2 < N && dist[t*2] == -1) {
            dist[t*2] = dist[t] + 1;
            q[++tt] = t * 2;
        }
        if (t - 1 >= 0 && dist[t-1] == -1) {
            dist[t-1] = dist[t] + 1;
            q[++tt] = t - 1;
        }
    }
    return -1;
}
int main() {
    cin >> n >> k;
    cout << bfs() << endl;
    return 0;
}