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

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.

题意：在一维的直线上，给出John的位置n，和cow的位置k，求出John按照给定三种规则找到cow的最少步数。

分析：用广度优先搜索从源点开始，依次用三种规则进行查找，设置边界条件，最先找到的即为最优解。这里还要注意下数组边界大小要比用于比较的边界要大一点，否则会数组越界而RE，我在这里吃了6个RE，一直没找到原因。后来才惊奇地发现时用于比较的MAX和数组大小Max相同。

import java.util.LinkedList;import java.util.Scanner;public class Main {	static int start, end;	static int MAX = 200000;	static LinkedList
     
       q;	static boolean[] visited;	static int[] step;	static int t, next;	static int bfs() {				q.add(start);		visited[start] = true;		step[start] = 0;		while (!q.isEmpty()) {			t = q.poll();						for (int i = 0; i < 3; i++) {				if (i == 0) {					next = t - 1;				} else if (i == 1) {					next = t + 1;				} else {					next = t * 2;				}				if (next > MAX || next < 0)					continue;				if (!visited[next]) {					q.add(next);					step[next] = step[t] + 1;					visited[next] = true;				}				if (next == end)					return step[next];			}		}		return -1;	}	public static void main(String[] args) {		Scanner sc = new Scanner(System.in);		q = new LinkedList
      
       ();		//在这个地方比MAX多加上5，放在RE		visited = new boolean[MAX+5];		step = new int[MAX+5];		start = sc.nextInt();		end = sc.nextInt();				if (start >= end) {			System.out.println(start - end);		} else {			System.out.println(bfs());		}	}}
      
     

版权声明：本文为博主原创文章，未经博主允许不得转载。