Catch That Cow#

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) on a 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#

Input	Output
`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.

1
#include<iostream>
2
#include<algorithm>
3
#include<queue>
4
using namespace std;
5
struct node{
6
  int x;
7
  int time;
8
};
9
int sx,ex;
10
int vis[100001];
11
int b[100001];//没用但是必不可少，缺了就会报runtime error
12
int bfs()
13
{
14
  queue<node>Q;
15
  node now,next;
16
  now.x=sx;
17
  now.time=0;
18
  Q.push(now);
19
  while(!Q.empty()){
20
    now=Q.front();
21
    if(now.x==ex)
22
    return now.time;
23
    if(now.x>0&&!b[now.x-1]){
24
      next.x=now.x-1;
25
      next.time=now.time+1;
26
      b[next.x]=1;
27
      Q.push(next);
28
    }
29
    if(now.x<ex&&!b[now.x+1]){
30
      next.x=now.x+1;
31
      next.time=now.time+1;
32
      b[next.x]=1;
33
      Q.push(next);
34
    }
35
    if(now.x<ex&&!b[now.x*2]){
36
      next.x=now.x*2;
37
      next.time=now.time+1;
38
      b[next.x]=1;
39
      Q.push(next);
40
    }
41
    Q.pop();
42
  }
43
}
44
int main(){
45

46
  cin>>sx>>ex;
47
  b[sx]=1;
48
  if(sx>=ex)
49
    cout<<sx-ex;
50
  else
51
  cout<<bfs();
52
  return 0;
53
}

音乐

音乐

Catch That Cow#

Input#

Output#

Sample#

Hint#

支持与分享

音乐

文章目录