题解：洛谷 P1588 [USACO07OPEN] Catch That Cow S

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

---

【题目来源】

洛谷：P1588 [USACO07OPEN] Catch That Cow S - 洛谷

【题目描述】

FJ 丢了一头牛，决定将其找回。FJ 和牛位于数轴上，初始位置分别为x xx和y yy，牛保持不动。每次移动时，若 FJ 处于位置p pp，他可移动至p + 1 p + 1p+1、p − 1 p - 1p−1或2 × p 2 \times p2×p。计算 FJ 抓住牛所需的最少移动次数。

【输入】

第一行为一个整数t ( 1 ≤ t ≤ 10 ) t\ ( 1\le t\le 10)t(1≤t≤10)，表示数据组数；

接下来每行包含一个两个正整数x , y ( 0 < x , y ≤ 10 5 ) x,y\ (0<x,y \le 10^5)x,y(0<x,y≤105)，分别表示 FJ 和牛的坐标。

【输出】

对于每组数据，输出最少步数，每组数据间用换行隔开。

【输入样例】

1 5 17

【输出样例】

4

【核心思想】

1. 问题分析：给定 FJ 初始位置x xx和牛的位置y yy（牛不动），FJ 每次可移动到p + 1 p+1p+1、p − 1 p-1p−1或2 p 2p2p。求抓住牛的最少移动次数。这是一个一维 BFS 最短路问题，关键在于将三种移动方式建模为边权为1 11的边，利用 BFS 的层序特性求最短路；同时需处理x ≥ y x \ge yx≥y时的特殊情况。

2. 算法选择：

   • BFS（广度优先搜索）：三种移动方式代价均为1 11，BFS 天然适合求无权图最短路
   • 特判优化：若x = y x = yx=y，答案为0 00；若x > y x > yx>y，只能一步步后退，答案为x − y x - yx−y
   • 距离数组：dis[p]记录到达位置p pp的最少步数，初始化为− 1 -1−1表示未访问

3. 关键步骤：

   • 读取输入：T TT组数据，每组x , y x, yx,y
   • 特判：
     • 若x = y x = yx=y：输出0 00
     • 若x > y x > yx>y：输出x − y x - yx−y
   • BFS 过程（x < y x < yx<y时）：
     • 初始化队列，d i s [ x ] = 0 dis[x] = 0dis[x]=0，x xx入队
     • 取出队首p pp，检查三种扩展：
       • p + 1 p+1p+1：若未越界且未访问，d i s [ p + 1 ] = d i s [ p ] + 1 dis[p+1] = dis[p] + 1dis[p+1]=dis[p]+1，入队
       • p − 1 p-1p−1：若未越界且未访问，d i s [ p − 1 ] = d i s [ p ] + 1 dis[p-1] = dis[p] + 1dis[p−1]=dis[p]+1，入队
       • 2 p 2p2p：若未越界且未访问，d i s [ 2 p ] = d i s [ p ] + 1 dis[2p] = dis[p] + 1dis[2p]=dis[p]+1，入队
     • 若扩展到达y yy，输出d i s [ y ] dis[y]dis[y]并结束
   • 输出答案

4. 时间/空间复杂度：

   • 时间复杂度：O ( T ⋅ max ⁡ ( x , y ) ) O(T \cdot \max(x, y))O(T⋅max(x,y))，每个位置最多入队一次
   • 空间复杂度：O ( max ⁡ ( x , y ) ) O(\max(x, y))O(max(x,y))，距离数组和队列

5. BFS 一维搜索的核心思想：

   • 状态空间离散化：将连续数轴上的位置离散为节点，三种移动为无向边（除2 p 2p2p为单向）
   • 层序扩展保证最优：BFS 按步数分层扩展，首次到达y yy时即为最少步数
   • 剪枝与边界：x > y x > yx>y时直接后退最优，避免无意义搜索；2 p 2p2p可能越界需严格限制在[ 0 , 10 5 ] [0, 10^5][0,105]内
   • 适用于"一维坐标上的最短步数"类问题，核心是建立状态转移图并用 BFS 求最短路

【解题思路】

【算法标签】

#普及- #BFS-一维

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intt,x,y;intvis[100005]={0},d[100005]={0};// vis数组用来标记该点是否来过，d数组用来表示到达该点的步数intmain(){cin>>t;// 输入t组while(t--){// 依次接受t组数据输入并处理cin>>x>>y;// 输入x和yqueue<int>q;// 定义队列memset(vis,0,sizeof(vis));// 初始化vis和d数组memset(d,0,sizeof(d));if(x==y){// 如果x与y重合cout<<0<<endl;// 说明牛和FJ在同一个位置，输出为0}if(x>y){// 如果x大于ycout<<x-y<<endl;// 则只能向后退，步数为x-y}if(x<y){// 如果x小于y，则使用广搜inttp=x;// 定义tp为x坐标vis[tp]=1;// 标记该点已经访问过q.push(tp);// 压入队列中while(!q.empty()){// 如果队列不为空inttp=q.front();// 取出队头q.pop();if(tp==y){// 广搜退出条件，即tp与y重合cout<<d[tp]<<endl;// 打印d[tp]，即到达tp这个点的步数break;// 退出循环，无需继续搜索}if(vis[tp+1]!=1&&tp+1>=0&&tp+1<=100000){// 对前进一步的位置进行边界判断及访问情况判断，符合条件再继续q.push(tp+1);// 前进一步位置压入队列vis[tp+1]=1;// 标记为访问过d[tp+1]=d[tp]+1;// 更新到达前进一步的步数}if(vis[tp-1]!=1&&tp-1>=0&&tp-1<=100000){// 对后退一步的位置进行边界判断及访问情况判断q.push(tp-1);// 后退一步位置压入队列vis[tp-1]=1;// 标记为访问过d[tp-1]=d[tp]+1;// 更新到达后退一步的步数}if(vis[tp*2]!=1&&tp*2>=0&&tp*2<=100000){// 对2*x的位置进行边界判断及访问情况判断q.push(tp*2);// 2*x位置压入队列vis[tp*2]=1;// 标记为访问过d[tp*2]=d[tp]+1;// 更新2*x位置的步数}}}}return0;}

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;intT,x,y,dis[N];// T: 测试用例数, (x,y): 起点终点, dis: 距离数组// 广度优先搜索voidbfs(){memset(dis,-1,sizeof(dis));// 初始化距离为-1dis[x]=0;// 起点距离为0queue<int>q;q.push(x);while(q.size()){intx=q.front();q.pop();if(x+1<N&&dis[x+1]==-1)// 前进一步{dis[x+1]=dis[x]+1;q.push(x+1);}if(x-1>0&&dis[x-1]==-1)// 后退一步{dis[x-1]=dis[x]+1;q.push(x-1);}if(x*2<N&&dis[x*2]==-1)// 走到2x位置{dis[x*2]=dis[x]+1;q.push(x*2);}if(x==y)// 到达终点{cout<<dis[y]<<endl;return;}}}intmain(){cin>>T;// 输入测试用例数while(T--){cin>>x>>y;// 输入起点和终点bfs();}return0;}

【运行结果】

1 5 17 4