抓住那头牛

问题描述

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

输入

两个整数，N和K

输出

一个整数，农夫抓到牛所要花费的最小分钟数

样例输入

5 17
3 5

样例输出

4
2

广度优先搜索:
策略一:给结点分层，起点是第0层，从起点最少只需n步就能到达的点属于第n层
策略二:用队列存结点
第一层:2 4 6
第二层:1 5
第三层:0

深搜:1-2-4-8-5-6-3-7
广搜:1-2-3-4-5-6-7-8

代码如下

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int N,K,Max = 100000;
    static Queue<Step>queue = new LinkedList<>();
    static boolean[]visit = new boolean[Max];//访问过设置为true

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        K = in.nextInt();
        bfs();
        in.close();
    }
    //广度优先搜索
    //分层进行遍历
    public static void bfs() {
        queue.add(new Step(N, 0));
        visit[N] = true;
        while(!queue.isEmpty()) {
            Step s = queue.poll();
            if(s.x==K) {//找到目标
                System.out.println(s.steps);return;
            }else {
                if(s.x-1>=0 && !visit[s.x-1]) {
                    queue.add(new Step(s.x-1, s.steps+1));
                    visit[s.x-1] = true;
                }
                if(s.x+1<=Max && !visit[s.x+1]) {
                    queue.add(new Step(s.x+1, s.steps+1));
                    visit[s.x+1] = true;
                }
                if(s.x*2<=Max && !visit[s.x*2]) {
                    queue.add(new Step(s.x*2, s.steps+1));
                    visit[s.x*2] = true;
                }
            }
        }
    }
}


class Step{
    int x;        //位置
    int steps;    //到达x所需的步数

    public Step(int x,int steps) {
        this.x = x;
        this.steps = steps;
    }
}