洛谷B3626 跳跃机器人

#先看题目

题目描述

地上有一排格子,共 n 个位置。机器猫站在第一个格子上,需要取第n 个格子里的东西。

机器猫当然不愿意自己跑过去,所以机器猫从口袋里掏出了一个机器人!这个机器人的行动遵循下面的规则:

  • 初始时,机器人位于 1 号格子
  • 若机器人目前在 x 格子,那么它可以跳跃到 x−1,x+1,2x 里的一个格子(不允许跳出界)

问机器人最少需要多少次跳跃,才能到达 n 号格子。

输入格式

仅一行,一个正整数,表示 n。

输出格式

仅一行,一个正整数,表示最少跳跃次数。

输入输出样例

输入 #1

30

输出 #1

6

输入 #2

50

输出 #2

7

输入 #3

64

输出 #3

6

输入 #4

63

输出 #4

8

说明/提示

样例解释

第一组样例:
1→2→4→8→16→15→301→2→4→8→16→15→30

第二组样例:
1→2→3→6→12→24→25→501→2→3→6→12→24→25→50

第三组样例:
1→2→4→8→16→32→641→2→4→8→16→32→64

第四组样例:
1→2→4→8→16→32→31→62→631→2→4→8→16→32→31→62→63

请注意在本组样例中,63 不能通过 64−1 得到,因为格子总数为 63 ,没有第 64 个格子。

数据规模与约定

对于 100% 的数据,有 1≤n≤1000000。

题目链接icon-default.png?t=N7T8https://www.luogu.com.cn/problem/B3626 

#思路 

要找最短路所以要用BFS。

#最后附上完整代码

#include<bits/stdc++.h>//万能头文件
using namespace std;
int vis[1000010],n;
queue<int> q;//定义队列
void bfs()
{
    memset(vis,-1,sizeof vis);
    q.push(1);
    vis[1]=0;
    while(!q.empty()){//队列不为空就一直执行
        int t=q.front();
        q.pop();
        if(t==n){//因为BFS是按层遍历所有第一次搜出的就是最短路
            cout<<vis[n];
            return;
        }
        if(t-1>=1&&t-1<=n&&vis[t-1]==-1){//搜过的地方不重复搜
            q.push(t-1);
            vis[t-1]=vis[t]+1;
        }
        if(t+1>=1&&t+1<=n&&vis[t+1]==-1){//注意边界
            q.push(t+1);
            vis[t+1]=vis[t]+1;
        }
        if(t*2>=1&&t*2<=n&&vis[t*2]==-1){
            q.push(t*2);
            vis[t*2]=vis[t]+1;
        }
    }
    return;
}
int main()
{
    cin>>n;
    bfs();
    return 0;//华丽收尾
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/482516.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于SpringBoot的大学生租房系统

开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea 系统展示 系统功能模块 系统首页界面图 用户…

有什么可以下载网页视频的浏览器插件 浏览器如何下载网页视频 网页视频怎么下载到本地 网页视频下载软件 IDM下载

在视频网站上看电影追剧&#xff0c;已经成为了大众生活中必不可少的一部分。为了保护自家视频的版权&#xff0c;很多平台都禁止用户下载会员视频。其实只要掌握了正确的方法&#xff0c;一样可以将会员视频下载到本地保存。那么有关有什么可以下载网页视频的浏览器&#xff0…

第十届蓝桥杯大赛个人赛省赛(软件类)真题- CC++ 研究生组-质数

17569 #include<stdio.h> #include<math.h> const int N 500000;//注意范围设大一点&#xff0c;还是有很多合数滴~ int f[N] {0}, p[N]; int main(){int num 1;for(int i 2; ; i){if(!f[i]){p[num] i;if(num 2020) break;for(int j i * i; j < N; j i…

Token的详解

Token的详解 文章目录 Token的详解前言:简介:使用token&#xff1a; 前言: 为什么会用到Token&#xff0c;因为cookie和session一些自身的缺点&#xff0c;限制了一些功能的实现&#xff0c;比如&#xff1a; cookie&#xff1a;优点是节省服务器空间&#xff0c;缺点不安全。…

数据结构面试常见问题之- Hashing - Hard Version

&#x1f600;前言 在解决哈希问题中的逆向情形时&#xff0c;我们面临着一种特殊挑战&#xff1a;已知散列函数和冲突解决策略的结果&#xff0c;需要推断输入元素的顺序。这种问题要求我们深入理解哈希函数的工作原理以及冲突处理的方式&#xff0c;并通过逆向思维来还原出元…

day43 动态规划part5

1049. 最后一块石头的重量 II 中等 提示 有一堆石头&#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合&#xff0c;从中选出任意两块石头&#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y&#xff0c;且 x < y。那么粉碎…

坚韧不拔,直至胜利的彼岸

当晨曦的第一缕光线透过夜幕的阴霾&#xff0c;希望与挑战并肩而来。在这个世界的每个角落&#xff0c;无数的个体都在经历着各自的斗争、失败、再斗争&#xff0c;直至最终的胜利。这是一个古老而永恒的循环&#xff0c;是成长的必经之路&#xff0c;它讲述着坚韧不拔的精神如…

【LeetCode】升级打怪之路 Day 26:回溯算法 — 集合划分问题

今日题目&#xff1a; 698. 划分为k个相等的子集 | LeetCode473. 火柴拼正方形 | LeetCode 参考文章&#xff1a; 经典回溯算法&#xff1a;集合划分问题 目录 LC 698. 划分为k个相等的子集 【classic&#xff0c;有难度】数据预处理&#xff1a;计算 target基本回溯优化 1&…

Zero-Change Object Transmission for Distributed Big Data Analytics——论文泛读

ATC 2022 Paper 问题 分布式大数据分析在很大程度上依赖于Java和Scala等高级语言的可靠性和多功能性。然而&#xff0c;这些高级语言也为数据传输制造了障碍。要在Java虚拟机&#xff08;JVM&#xff09;之间传输数据&#xff0c;发送方应将对象转换为字节数组&#xff08;序…

校验注解@Length提示Length.class 类文件具有错误的版本 55.0, 应为 52.0

你们好&#xff0c;我是金金金。 场景 我正在学习参数校验&#xff0c;启动项目时报错如下 实体类 依赖版本 报错信息 排查 看报错信息提示类文件具有错误的版本 55.0, 应为 52.0&#xff0c;猜测可能是版本的问题。 可以确实就是版本的关系了&#xff0c;8.0版本的只能在jd…

2024年基于springboot+vue的10个最新选题推荐

前言 &#x1f497;博主介绍&#xff1a;✌专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f447;&#x1f3fb; 精彩专栏 推荐订阅&#x1f447;&#x1f3fb; 2024年Java精品实战案例《100套》 &#x1f345;文末获取源码联系&#x1f345; &#x1f31f…

VMware Fusion Pro 13:一站式虚拟化解决方案,满足多样化需求

VMware Fusion Pro 13是一款功能强大的虚拟机软件&#xff0c;专为Mac操作系统设计。它支持在Mac电脑上创建和管理多个虚拟计算机&#xff0c;允许用户在不同操作系统中进行软件测试、开发和部署&#xff0c;如Windows、Linux等。该软件采用了最新的虚拟化技术&#xff0c;能够…

逻辑 | 逻辑先修营

学习到更新日期逻辑先修营-3常见逻辑连词及逻辑表达2024-3-23 1.形式逻辑基础1 2.形式逻辑基础2 3.常见逻辑连词及逻辑表述 4.OR相关考点 5.AND相关考点 6.逻辑箭头基本考点1 7.逻辑箭头基本考点2 8.代入逻辑推理事实真1 9.代入逻辑推理事实真2 10.形式逻辑四大基本考点…

VUE3 Day12pinia

属性在解构时需要用到storeToRefs语法&#xff0c;而方法则不需要 官方文档&#xff1a;https://prazdevs.github.io/pinia-plugin-persistedstate/zh/ 如果不配将使用pinia的默认配置

用Kimichat学习王庆法老师关于Sora的文章

目录 一 引言:二 提示词方面:三 与Kimi的聊天记录我:假如你是一名大模型方面的专家,提取一下这篇文章的核心观点,用三列表格的形式,https://mp.weixin.qq.com/s/Y-vmxmPu4_-tHaeP35hDJg我:上述文章的一、Spacetime Latent Patches 潜变量时空碎片, 建构视觉语言系统部分…

设计模式及其在项目、框架中的应用

设计模式的作用&#xff1a; 1、类之间关系图&#xff0c;明确的角色及其关系、作用&#xff1b; 2、符合开闭原则&#xff0c;职责明确&#xff0c;并且开放的拓展点可以有效应对后期的变化。 &#xff08;一&#xff09;、责任链模式 适用场景&#xff1a; 在一个流程中&…

ArmSoM-Sige RK3588开发板产品简介

让我们在 5 分钟内了解 Sige7。 简介​ ArmSoM-Sige7采用Rockchip RK3588新一代旗舰级八核64位处理器&#xff0c;主频高达2.4GHz&#xff0c;6 TOPS算力NPU&#xff0c;最大可配32GB大内存。支持8K视频编解码&#xff0c;拥有丰富的接口&#xff0c;支持双2.5G网口、WiFi6 &…

Tomcat9.0.87闪退解决方案

运行Tomcat9.0.87闪退 报错&#xff1a;Neither the JAVA_HOME nor the JRE_HOME environment variable is defined At least one of these environment variable is needed to run this program 原因&#xff1a;使用了免安装的方法&#xff0c;直接运行bin目录下的startup.ba…

unity学习(68)——相机/模型的旋转/位置计算

这个比想象中要难&#xff0c;而且需要自己写。 1.相机可以转xy两个位置&#xff0c;可以点头和转圈。注意这里有一个if判断&#xff08;后面返回来发现了这些问题&#xff09; 2.角色不能点头&#xff0c;只能转圈。 难得是移动方向&#xff0c;因为移动方向(位置)和转向是相…

无人机三维建模过程中注意事项

无人机三维建模是指利用无人机技术进行三维建模&#xff0c;该方法通过无人机搭载的多种传感器&#xff0c;如摄像头、激光扫描仪等&#xff0c;获取建筑物的多角度影像数据&#xff0c;然后利用计算机视觉技术和三维重建算法&#xff0c;将这些影像数据转化为高精度的三维模型…