【Java每日一题,BFS】Catch That Cow

简介: 【Java每日一题,BFS】Catch That Cow

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

相关文章
|
6月前
|
存储 算法 Java
Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点,而BFS利用队列按层次访问。以下是简化的代码片段:[Java代码略]
48 4
|
7月前
|
算法 Java
BFS(广度搜索|宽度搜索)无向图遍历(JAVA手把手深入解析)
BFS(广度搜索|宽度搜索)无向图遍历(JAVA手把手深入解析)
141 0
|
Java 程序员 编译器
[java进阶]——异常详解,try catch捕获异常,抛出异常
[java进阶]——异常详解,try catch捕获异常,抛出异常
159 0
|
Java
数据结构(11)图的遍历,DFS、BFS的JAVA实现
11.1.图的遍历 图的遍历,即将图内所有顶点都访问一遍。 有两种遍历方式: BFS DFS 以下图的遍历为例:
99 0
Java 最常见的面试题:try-catch-finally 中,如果 catch 中 return 了,finally 还会执行吗?
Java 最常见的面试题:try-catch-finally 中,如果 catch 中 return 了,finally 还会执行吗?
|
Java 数据库连接
【Java基础】[异常处理]try,catch,finally
【Java基础】[异常处理]try,catch,finally
130 0
|
算法 Java
二叉树最大宽度(java 算法 bfs)
二叉树最大宽度(java 算法 bfs)
164 0
二叉树最大宽度(java 算法 bfs)
|
人工智能 Java BI
力扣207:课程表(Java拓扑排序:bfs+dfs)
力扣207:课程表(Java拓扑排序:bfs+dfs)
137 0
力扣200:岛屿数量(Java dfs+bfs)
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
126 0