Catch That Cow
描述
农夫约翰已得知一头逃犯母牛的位置，他想立即抓住她。他从N (0 ≤ N ≤ 100,000)点开始,母牛在同一数字线上的K(0 ≤ K ≤ 100,000)点。
农夫约翰有两种交通方式：步行和心灵传送:
步行：FJ可以在一分钟内从任意点X移动到点X-1或X+1
传送：FJ可以在一分钟内从任意点X移动到点2*X。
如果母牛没有意识到它的追赶，根本就不动，农夫约翰要花多长时间才能找回它？
输入
第1行：两个空格分隔的整数：N和K
输出
第1行：农夫约翰抓住逃犯的母牛所需的时间最少，以分钟为单位。
Sample Input
5 17
Sample Output
4
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
/**
*
* @author XA-GDD
*
*/
public class Main{
static int N,K;
static int [] moveStep = {1,-1,0};
static int _Max_K = 100000;
static boolean [] visited = new boolean [100003];
static int [] minCost = new int [100003];
public static void main(String[] args) throws IOException {
Scanner reader=new Scanner(System.in);
N=reader.nextInt();
K=reader.nextInt();
reader.close();
if (N >= K) {
System.out.println(N - K); //农夫比牛远时，只能往回走，即距离需要减少，而走的方式时，减少的只有-1
}else {
System.out.println(bfs(N,K));
}
}
static int bfs(int start , int end) {
int minStep = 0;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1]-o2[1];
}
});
Arrays.fill(visited,false);
Arrays.fill(minCost,Integer.MAX_VALUE>>1);
pq.add(new int[] {start,0});
minCost[start] = 0;
while(!pq.isEmpty()) {
int curr[] = pq.poll();
if(curr[0] == end ) {
minStep = curr[1];
break;
}
if(visited[curr[0]]) {
continue;
}
visited[curr[0]]=true;
for(int i=0;i<moveStep.length;i++) {
int nextNode = 0;
if(moveStep[i]==0) {
nextNode = curr[0]*2;
}else {
nextNode = curr[0]+moveStep[i];
}
if(nextNode<=_Max_K && nextNode>0) {
if(minCost[curr[0]]+1<minCost[nextNode]) {
minCost[nextNode]=minCost[curr[0]]+1;
pq.add(new int[] {nextNode,minCost[nextNode]});
}
}
}
}
return minStep;
}
}