Catch That Cow (BFS)

Catch That Cow

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 33021 Accepted Submission(s): 8956

Problem Description

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

5 17

Sample Output

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.

Source

USACO 2007 Open Silver

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 using namespace std;
 6 #define scanf scanf_s
 7 const int N = 1000000;
 8 
 9 struct node {
10     int x, step;
11 };
12 int n, k;
13 bool vis[N+10];
14 
15 int check(int x) {
16     if (x < 0 || x >= N || vis[x]) return 0;
17     else return 1;
18 }
19 
20 
21 int bfs(int x) {
22     memset(vis, 0, sizeof(vis));
23     queue<node> q;
24     node a;
25     a.x = x; a.step = 0; vis[a.x] = 1;
26     q.push(a);
27     while (!q.empty()) {
28         node a = q.front();
29         q.pop();
30         if (a.x == k) return a.step;
31         node nxt = a;
32         nxt.x = a.x + 1;
33         if (check(nxt.x)) {
34             nxt.step = a.step + 1;
35             vis[nxt.x] = 1;
36             q.push(nxt);
37         }
38         nxt.x = a.x - 1;
39         if (check(nxt.x)) {
40             nxt.step = a.step + 1;
41             vis[nxt.x] = 1;
42             q.push(nxt);
43         }
44         nxt.x = a.x * 2;
45         if (check(nxt.x)) {
46             nxt.step = a.step + 1;
47             vis[nxt.x] = 1;
48             q.push(nxt);
49         }
50     }
51     return -1;
52 
53 }
54 
55 int main() {
56     int ans;
57     while (~scanf("%d%d", &n, &k))
58     {
59         ans = bfs(n);
60         printf("%d
", ans);
61     }
62 
63 
64     return 0;
65 }