Introduction
张三想吃一顿全牛宴,所以用地上捡的石头雇佣傻子去为他抓牛
你可以将图视为一条只有x的坐标的轴
而你作为神通广大的傻子拥有两个能力
你可以让牛当前位置由x变为x+1或者x-1
你可以让牛当前位置由x变为2*x
你能得出你最少需要多少次操作能将牛赶往指定地点吗？
Input
输入包含两个数字n，k分别代表牛的起始位置和目标地点的x坐标。
n，k均大于等于0且小于等于100000
Output
输出最少的操作次数
Sample
input
5 17
output
4
Solution
package week3; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; /** * @author liangyuanshao * @date 2022/5/3 - 18:05 */ class Location{ int now; int step; public Location(int now, int step) { this.now = now; this.step = step; } } public class Main5 { //为什么标记的长度是133334，就是当前坐标乘2之后和k的距离，不可能超过当前坐标和k的距离 static boolean[] flag=new boolean[133334]; public static int dfs(int n,int k){ //首先创建队列 LinkedList<Location> queue=new LinkedList(); queue.offer(new Location(n,0)); flag[n]=true; //进入循环 while (!queue.isEmpty()){ //取出首元素 Location top=queue.poll(); if(top.now==k){ return top.step; } //然后进行各种情况的判断，每种情况都要判断是否合理，合理的判断方式有：是否越界，是否已经入过队列 int nextX; nextX=top.now-1; if(nextX>=0&&!flag[nextX]){ queue.offer(new Location(nextX,top.step+1)); flag[nextX]=true; } nextX=top.now+1; if(nextX<133334&&!flag[nextX]){ queue.offer(new Location(nextX,top.step+1)); flag[nextX]=true; } nextX=top.now*2; if(nextX<133334&&!flag[nextX]){ queue.offer(new Location(nextX,top.step+1)); flag[nextX]=true; } } return 0; } public static void main(String[] args) { Scanner s=new Scanner(System.in); int n=s.nextInt();int k=s.nextInt(); if(k<=n){ System.out.println(n-k); }else { System.out.println(dfs(n,k)); } } }
Experience
第一次系统的学习BFS，参考的https://hanhan.blog.csdn.net/article/details/104204397
