Problem C POJ 3278 Catch That Cow(三入口bfs)

C - Catch That Cow

Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

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.

题目大意：

　　给你一个数字n,n<=100000，然后，再给你一个数字k，求把k变成n所需要的最小的步数.

解题思路：

　　看到最小步数，想都不都想直接bfs，因为bfs是能够把我们在第N步的N个状态全部扩展出来，所以找起来更快

　　一开始wa了一发，原因是对于n==k的情况，答案应该是0的，但是我的程序跑出来却是2，原因就是把bfs写惨了

　　每次在进start的时候，判断下就好了、

代码：

 1 # include<cstdio>
 2 # include<iostream>
 3 # include<cstring>
 4 # include<queue>
 5 
 6 using namespace std;
 7 
 8 # define MAX 100000+4
 9 
10 struct node
11 {
12     int x;
13     int step;
14 };
15 queue<node>Q;
16 
17 int book[MAX];
18 int n,k;
19 
20 void init()
21 {
22     while ( !Q.empty() )
23     {
24         Q.pop();
25     }
26     memset(book,0,sizeof(book));
27 }
28 
29 int bfs ( node start )
30 {
31     init();
32     Q.push(start);
33     if ( start.x==k )
34         return start.step;
35     while (!Q.empty())
36     {
37         node now = Q.front();
38         Q.pop();
39         int tx = 0;
40         for ( int i = 0;i < 3;i++ )
41         {
42             if ( i == 0 )
43                 tx = now.x-1;
44             else if ( i==1 )
45                 tx = now.x+1;
46             else
47                 tx = 2*now.x;
48             if ( tx > MAX||book[tx]==1 )
49                 continue;
50             if ( tx==k )
51                 return now.step+1;
52             node newnode;
53             if ( book[tx]==0 )
54             {
55                 book[tx] = 1;
56                 newnode.x = tx; newnode.step = now.step+1;
57                 Q.push(newnode);
58             }
59         }
60     }
61 }
62 
63 
64 int  main(void)
65 {
66     while ( scanf("%d%d",&n,&k)!=EOF )
67     {
68         book[n] = 1;
69         node start;
70         start.step = 0; start.x = n;
71         int ans = bfs(start);
72         printf("%d
",ans);
73     }
74 
75     return 0;
76 }