目录
1.题目2.思路3.代码
1.题目
农夫知道一头牛的位置，想要抓住它。
农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。
农夫有两种移动方式：
从 X 移动到 X−1 或 X+1，每次移动花费一分钟 从 X 移动到 2∗X，每次移动花费一分钟 假设牛没有意识到农夫的行动，站在原地不动。
农夫最少要花多少时间才能抓住牛？
输入格式 共一行，包含两个整数N和K。
输出格式 输出一个整数，表示抓到牛所花费的最少时间。
数据范围 0≤N,K≤105 输入样例： 5 17 输出样例： 4
2.思路
题目讲述一共有3种移动情况且权重一致
从 X 移动到 X−1
从 X 移动到 X+1
从 X 移动到 2∗X
相当于X 与X - 1,X + 1,2 * X ,各连一条边,从n开始进行bfs到k，dist[k]表示k点到n点的最短距离
3.代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std
;
const int N
=2e5+10;
int dist
[N
], q
[N
];
int n
,k
;
int bfs()
{
memset(dist
,-1,sizeof dist
);
int hh
=0,tt
=0;
q
[0]=n
;
dist
[n
]=0;
while(hh
<=tt
)
{
int t
=q
[hh
++];
if(t
==k
) return dist
[k
];
if(t
+1<N
&&dist
[t
+1]==-1)
{
dist
[t
+1]=dist
[t
]+1;
q
[++tt
]=t
+1;
}
if(t
-1>=0&&dist
[t
-1]==-1)
{
dist
[t
-1]=dist
[t
]+1;
q
[++tt
]=t
-1;
}
if(t
*2<N
&&dist
[t
*2]==-1)
{
dist
[t
*2]=dist
[t
]+1;
q
[++tt
]=t
*2;
}
}
return -1;
}
int main()
{
cin
>>n
>>k
;
cout
<<bfs()<<endl
;
return 0;
}
