题目描述
FJ 丢失了他的一头牛，他决定追回他的牛。已知 FJ 和牛在一条直线上，初始位置分别为 x 和 y，假定牛在原地不动。FJ 的行走方式很特别：他每一次可以前进一步、后退一步或者直接走到 2×x 的位置。计算他至少需要几步追上他的牛。
输入格式
第一行为一个整数 t (1≤t≤10)，表示数据组数；
接下来每行包含一个两个正整数 x,y (0<x,y≤105)，分别表示 FJ 和牛的坐标。
输出格式
对于每组数据，输出最少步数。
输入输出样例
输入 #1
1 5 17
输出 #1
4
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;// 定义常量 N，用于数组大小的定义，确保数组足够大以容纳可能的最大值
const int N = 2e5 + 10 + 2e5;// 全局变量声明
int n, k; // n 和 k 分别表示起始位置和目标位置
int d; // 测试用例的数量
int q[N]; // 队列，用于广度优先搜索 (BFS) 的节点存储
int dist[N]; // 记录从起点到每个点的距离/*** bfs 函数：使用广度优先搜索算法计算从起点 n 到终点 k 的最短距离。* * @return 返回从起点 n 到终点 k 的最短距离，如果无法到达则返回 -1。*/
int bfs()
{// 初始化距离数组，所有位置初始设为 -1 表示未访问memset(dist, -1, sizeof(dist));// 起点 n 的距离设为 0dist[n] = 0;// 将起点加入队列q[0] = n;// 队列的头指针 hh 和尾指针 tt 初始化为 0int hh = 0, tt = 0;// 当队列不为空时继续搜索while (hh <= tt){// 取出队列头部元素int t = q[hh++];// 如果当前节点是目标节点 k，返回其距离if (t == k) return dist[t];// 检查并处理 t+1 这个位置if (t + 1 <= k && dist[t + 1] == -1) {// 更新距离并将其加入队列dist[t + 1] = dist[t] + 1;q[++tt] = t + 1;}// 检查并处理 t-1 这个位置if (t - 1 >= 0 && dist[t - 1] == -1){// 更新距离并将其加入队列dist[t - 1] = dist[t] + 1;q[++tt] = t - 1;}// 检查并处理 t*2 这个位置if (t * 2 < N && dist[t * 2] == -1){// 更新距离并将其加入队列dist[t * 2] = dist[t] + 1;q[++tt] = t * 2;}}// 如果遍历完所有可达节点仍未找到目标节点 k，返回 -1return -1;
}/*** main 函数：程序入口，读取输入并调用 bfs 函数计算结果。*/
int main()
{// 读取测试用例数量 dcin >> d;// 对每个测试用例进行处理while (d--){// 读取起点 n 和目标位置 kcin >> n >> k;// 调用 bfs 函数计算最短距离并输出结果cout << bfs() << endl;}return 0;
}