抓住那头牛
↑ 题目链接
题目
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点 \(N\) ，牛位于点 \(K\)。农夫有两种移动方式：从 \(X\) 移动到 \(X−1\) 或 \(X+1\) ，每次移动花费一分钟从 \(X\) 移动到 \(2∗X\)，每次移动花费一分钟假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
输入格式
共一行，包含两个整数 \(N\) 和 \(K\)。
输出格式
输出一个整数，表示抓到牛所花费的最少时间。
数据范围
\(0≤N,K≤10^5\)
输入样例：
5 17
输出样例：
4
思路
\(BFS\) 搜索即可，每次扩展题目里的三种状态，注意不要越界
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int d[N];
int n,k;
int bfs()
{
memset(d,-1,sizeof d);
queue<int>q;
d[n]=0;
q.push(n);
while(q.size())
{
int t=q.front();
q.pop();
if(t==k)return d[t];
if(t+1<N&&d[t+1]==-1)
{
d[t+1]=d[t]+1;
q.push(t+1);
}
if(t-1>=0&&d[t-1]==-1)
{
d[t-1]=d[t]+1;
q.push(t-1);
}
if(t*2<N&&d[t*2]==-1)
{
d[t*2]=d[t]+1;
q.push(t*2);
}
}
}
int main()
{
cin>>n>>k;
cout<<bfs()<<endl;
return 0;
}