题目描述

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

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

农夫有两种移动方式：

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

农夫最少要花多少时间才能抓住牛？

样例

输入样例：
5 17
输出样例：
4

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N = 200010;
int n, k;
int dist[N];
int bfs()
{
    queue<int> q;
    q.push(n);
    dist[n] = 0;
    while (q.size())
    {
        int t = q.front();
        q.pop();
        if (t == k) return dist[t];//判断优化
        if (dist[t + 1] == -1) q.push(t + 1), dist[t + 1] = dist[t] + 1;
        if (t - 1 >= 0 && dist[t - 1] == -1) q.push(t - 1), dist[t - 1] = dist[t] + 1;
        if (t * 2 < N && dist[t * 2] == -1) q.push(t * 2), dist[t * 2] = dist[t] + 1;//注意数组下标越界问题
    }
    return -1;
}
int main()
{
    cin >> n >> k;
    memset(dist, -1, sizeof(dist));
    cout << bfs()  << endl;
    return 0;
}