题目描述 农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。
农夫有两种移动方式：
从 X 移动到 X − 1 或 X + 1，每次移动花费一分钟
从 X 移动到 2X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动，农夫最少要花多少时间才能抓住牛？
输入格式 两个整数，N 和 K。
输出格式 一个整数，农夫抓到牛所要花费的最小分钟数。
输入样例 5 17
输出样例 4
数据范围 0 ≤ N, K ≤ 100,000
题解 BFS：
#include <iostream> #include <cstring> #include <queue> using namespace std; const int N = 100010; int n, k; int dist[N]; int bfs() { memset(dist, -1, sizeof dist); queue<int> q; q.push(n); dist[n] = 0; while(q.size()) { int t = q.front(); q.pop(); if(t == k) return dist[k]; if(t + 1 <= N && 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; } } } int main() { cin >> n >> k; cout << bfs() << endl; return 0; }