当前位置：网站首页>Catch That Cow (detailed)

Catch That Cow (detailed)

2022-07-30 04:42:00 【_rosy】

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) ona number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K

Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample

InputcopyOutputcopy
5 17
4

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

When you first see this kind of question, you should think of breadth-first search, because here is to constantly test which one can reach the destination, and to judge the shortest number of steps. The shortest number of steps can be well judged through the queue.Because the queue is first-in, first-out, and in this question, each trial x-1, x+1, x*2 is an equal trial, and each time is the previous one plus 1, so the same when walkingThere is a situation where the number of steps has reached the end point, which is the shortest number of steps, because it is impossible for a y=x-1d to be equal to x+1 or x*2 at the same time, right, so when they are all threeUnder the same number of steps, there is a situation that comes first, that is the minimum number of steps

#include#include#include#include#include#include#includeusing namespace std;int vis[200005];struct node{int x,step;};queueq;int bfs(int x,int y){node start,next,now;start.x=x,start.step=0;//Initializationvis[x]=1;q.push(start);while(!q.empty()){now=q.front();//Equivalent to an intermediate variable, retain the previous valueif(now.x==y){return now.step ;}q.pop(); //First judge whether the destination is reached, if not, go out, because its value has been reservedif(now.x-1>=0&&!vis[now.x-1]){next.x=now.x-1;next.step=now.step+1;vis[now.x-1]=1;q.push(next);}if(now.x+1<=y&&!vis[now.x+1]){next.x=now.x+1;next.step=now.step+1;//The now.step here is a value with the previous if and the next if condition,//This is to ensure that these three steps are all under one step, and whoever arrives first in the next step is the shortestvis[now.x+1]=1;q.push(next);}if(now.x<=y&&!vis[now.x*2]){ //Be careful not to be now.x*2<=y//because if that's the case it's not out of scope by itself, but it'll take one less step herenext.x=now.x*2;next.step=now.step+1;vis[now.x*2]=1;q.push(next);}}}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;cout<

原网站

版权声明
本文为[_rosy]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/211/202207300435094924.html

边栏推荐

猜你喜欢

随机推荐