Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a pointN (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 orX + 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

题目大意：农夫在n的位置，牛在k的位置，牛不动，若农夫任意时间在X，农夫可走到X+1，X-1,2*X三个位置，问农夫几次可抓到牛

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

public class POJ3278_ieayoio {
	public static boolean[] f;

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			int n = cin.nextInt();
			int k = cin.nextInt();
			System.out.println(bfs(n, k));
		}
	}

	static int bfs(int n, int k) {
		// Queue
  
    queue = new LinkedList
   
    (); Queue
    
      queue = new ArrayDeque
     
      (); f = new boolean[100010]; Arrays.fill(f, true);//标记是否曾走过 Node node = new Node(n, 0); f[n] = false; queue.offer(node);//初始值直接入队 while (!queue.isEmpty()) { node = queue.poll();//出队 if (node.location == k) { return node.step; } Node el; if (node.location < k && f[node.location + 1]) { el = new Node(node.location + 1, node.step + 1); f[node.location + 1] = false; queue.offer(el); } if (node.location - 1 >= 0 && f[node.location - 1]) { el = new Node(node.location - 1, node.step + 1); f[node.location - 1] = false; queue.offer(el); } //当node.location大于k是只能选择后退 //node.location * 2 <= 100000是坐标轴的范围，开始没加就Runtime Error了 if (node.location < k && node.location * 2 <= 100000 && f[node.location * 2]) { el = new Node(node.location * 2, node.step + 1); f[node.location * 2] = false; queue.offer(el); } } return node.step; } } class Node { int location;//位置 int step;//步数 Node(int location, int step) { this.location = location; this.step = step; } }