Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 41703 | Accepted: 13005 |
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
Output
Sample Input
5 17
Sample Output
4
Hint
Source
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55 |
import java.awt.Point; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Bfs{ private
static final int SIZE= 200000 ; private
int s, t; private
boolean [] vis; private
Queue<Point> q; public
Bfs( int s, int t){ this .s=s; this .t=t; q = new
LinkedList<Point>(); vis = new
boolean [SIZE]; for ( int
i= 0 ; i<SIZE; i++) vis[i]= false ; } public
int run(){ q.add( new
Point(s, 0 )); while (!q.isEmpty()){ Point cur = q.poll(); if (cur.x == t) return
cur.y; int
y = cur.y+ 1 ; if (cur.x> 0
&& !vis[cur.x- 1 ]){ q.add( new
Point(cur.x- 1 ,y)); vis[cur.x- 1 ]= true ; } if ((cur.x<< 1 )<SIZE && !vis[cur.x<< 1 ]){ q.add( new
Point(cur.x<< 1 ,y)); vis[cur.x<< 1 ]= true ; } if (cur.x+ 1 <SIZE && !vis[cur.x+ 1 ]){ q.add( new
Point(cur.x+ 1 , y)); vis[cur.x+ 1 ]= true ; } } return
SIZE>> 1 ; } } public
class Main { static
final int INF = 200000 ; /** * @param args */ public
static void main(String[] args) { // TODO Auto-generated method stub Scanner s = new
Scanner(System.in); while (s.hasNext()){ int
n = s.nextInt(), k=s.nextInt(); Bfs bfs = new
Bfs(n,k); System.out.println(bfs.run()); } } } |
原文:http://www.cnblogs.com/ramanujan/p/3582822.html