P1588 [USACO07OPEN] Catch That Cow S 洛谷 BFS-最短路思想

题目描述

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 的距离设为 0
    dist[n] = 0;
    
    // 将起点加入队列
    q[0] = n;
    
    // 队列的头指针 hh 和尾指针 tt 初始化为 0
    int 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，返回 -1
    return -1;
}

/**
 * main 函数：程序入口，读取输入并调用 bfs 函数计算结果。
 */
int main()
{
    // 读取测试用例数量 d
    cin >> d;
    
    // 对每个测试用例进行处理
    while (d--)
    {
        // 读取起点 n 和目标位置 k
        cin >> n >> k;
        
        // 调用 bfs 函数计算最短距离并输出结果
        cout << bfs() << endl;
    }
    
    return 0;
}