POJ 3278 题解

Catch That Cow

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 78114		Accepted: 24667

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 "fstream"
 3 #include "sstream"
 4 #include "cstdio"
 5 #include "queue"
 6 
 7 using namespace std ;
 8 const int maxN = 1e5 + 1e3 ; 
 9 const int Max_Limit = 1e5 ; 
10 const int INF = 2147483647 ;
11 typedef long long QAQ ;
12 
13 queue < int > Q ; 
14 bool vis[ maxN ] ;
15 int step[ maxN ] ;
16 int K , N ;
17 
18 bool Check ( int x_x ) { return x_x == K ? true : false ; }
19 
20 int BFS ( ) {
21         int temp ;
22         bool Get_Target = false ; 
23         Q.push ( N ) ;
24         vis[ N ] = true ;
25         while ( !Q.empty ( ) ) {
26                 int tmp = Q.front ( ) ;
27                 Q.pop ( ) ;
28                 for ( int i=0 ; i<3 ; ++i ) {
29                         switch ( i ) {
30                                 case 0 :{
31                                         temp = tmp - 1 ;
32                                         break;
33                                 }
34                                 case 1 :{
35                                         temp = tmp + 1 ;
36                                         break;
37                                 }
38                                 case 2 :{
39                                         temp = tmp * 2 ;
40                                         break;
41                                 }
42                         }
43                         
44                         if ( temp > Max_Limit || temp < 0 ) continue ; 
45                         if ( !vis[ temp ] ) {
46                                 Q.push( temp ) ;
47                                 step[ temp ] = step[ tmp ] + 1 ;
48                                 vis[ temp ] = true ;
49                                 if ( Check ( temp ) ) {
50                                         Get_Target = true ; 
51                                         return step[ temp ] ;
52                                 }
53                         }
54                 }
55         }
56         if ( !Get_Target ) return -1 ; 
57 }
58 
59 int main ( ) {
60         scanf ( "%d %d" , &N , &K ) ;
61         if ( N >= K ) {
62                 printf ( "%d
" , N - K ) ;
63                 goto End ;
64         }
65         printf ( "%d
" , BFS ( ) ) ;
66         End : 
67                 return 0 ;
68 }

View Code

2016-10-19 21:59:12