当前位置: 首页 > news >正文

一维坐标的移动(bfs)

在一个长度为n的坐标轴上,小S想从A点移动B点。

他的移动规则如下:

向前一步,坐标增加1。

向后一步,坐标减少1。

跳跃一步,使得坐标乘2。

小S不能移动到坐标小于0或大于n的位置。

小S想知道从A点移动到B点的最少步数是多少,你能帮他计算出来么?

输入格式

第一行输入三个整数n,A,B,分别代表坐标轴长度,起始点坐标,终点坐标。(0<=A,B<=n<=50000)

输出格式

输出一个整数占一行,代表小S要走的最少步数。

样例输入

10 2 7

样例输出

3

dfs深度优先(时间复杂度会比较高,这里仅供理解题目)

#include<iostream>
using namespace std;
const int N=50005;
bool st[N];
int n,A,B;
int ans;
void dfs(int x,int step){if(x==B){//结束条件 ans=step;return;}int y;//向前走,坐标+1y=x+1;if(!st[y]&&y>=1&&y<=n){st[y]=true;dfs(y,step+1);st[y]=false;}//向后走,坐标-1y=x-1;if(!st[y]&&y>=1&&y<=n){st[y]=true;dfs(y,step+1);st[y]=false;}//跳跃,坐标*2 y=x*2;if(!st[y]&&y>=1&&y<=n){st[y]=true;dfs(y,step+1);st[y]=false;}
}
int main(){cin>>n>>A>>B;dfs(A,0);cout<<ans<<endl;return 0;
}

bfs广度优先

 

#include<iostream>
#include<queue>
using namespace std;
const int N=50005;
bool st[N];
typedef struct point{int x;int step;
}point;
queue<point> q;
int n,A,B;void bfs(){while(q.size()){point p=q.front();if(p.x==B){break;}point next;int a;//向前走,坐标+1 a=p.x+1;if(!st[a]&&a>=1&&a<=n){next.x=a;next.step=p.step+1;q.push(next);//入队st[a]=true; }//向后走,坐标-1 a=p.x-1;if(!st[a]&&a>=1&&a<=n){next.x=a;next.step=p.step+1;q.push(next);//入队st[a]=true; }//跳跃,坐标*2 a=p.x*2;if(!st[a]&&a>=1&&a<=n){next.x=a;next.step=p.step+1;q.push(next);//入队st[a]=true; }q.pop(); }
}
int main(){cin>>n>>A>>B;point start;start.x=A;start.step=0;q.push(start);bfs();cout<<q.front().step<<endl;return 0;
} 

 

相关文章:

一维坐标的移动(bfs)

在一个长度为n的坐标轴上&#xff0c;小S想从A点移动B点。 他的移动规则如下&#xff1a; 向前一步&#xff0c;坐标增加1。 向后一步&#xff0c;坐标减少1。 跳跃一步&#xff0c;使得坐标乘2。 小S不能移动到坐标小于0或大于n的位置。 小S想知道从A点移动到B点的最少步数是多…...

面试题 整理

第1题&#xff1a;常见数据类型大小 这边以64位计算机系统&#xff0c;环境而言。 类型 存储大小 值范围 char 1 字节 -128 到 127 或 0 到 255 unsigned char 1 字节 0 到 255 signed char 1 字节 -128 到 127 int 4 字节 -32,768 到 32,767 或 -2,147,483,648…...

苍穹外卖-day08:导入地址簿功能代码(单表crud)、用户下单(业务逻辑)、订单支付(业务逻辑,cpolar软件)

苍穹外卖-day08 课程内容 导入地址簿功能代码用户下单订单支付 功能实现&#xff1a;用户下单、订单支付 用户下单效果图&#xff1a; 订单支付效果图&#xff1a; 1. 导入地址簿功能代码&#xff08;单表crud&#xff09; 1.1 需求分析和设计 1.1.1 产品原型&#xff08…...

Java面试相关问题

一.MySql篇 1优化相关问题 1.1.MySql中如何定位慢查询&#xff1f; 慢查询的概念&#xff1a;在MySQL中&#xff0c;慢查询是指执行时间超过一定阈值的SQL语句。这个阈值是由long_query_time参数设定的&#xff0c;它的默认值是10秒1。也就是说&#xff0c;如果一条SQL语句的执…...

Linux Shell中的循环控制语句

Linux Shell中的循环控制语句 在编写Shell脚本时&#xff0c;循环是一种常用的控制结构&#xff0c;用于重复执行一系列命令。在Shell中&#xff0c;主要有三种循环控制语句&#xff1a;for循环&#xff0c;while循环&#xff0c;和until循环。 1. For循环 for循环是最常见的…...

proto3语言指南

Language Guide (proto3) 本指南介绍了如何使用 protocol buffer 语言来构建protocol buffer数据,包括.proto文件语法以及如何从.proto 文件生成数据访问类。它涵盖了proto3 版本的协议缓冲语言:有关proto2语法的信息,请参阅proto2语言指南。 文章目录 Language Guide (pro…...

解决后端传给前端的日期问题

解决方式&#xff1a; 1). 方式一 在属性上加上注解&#xff0c;对日期进行格式化 但这种方式&#xff0c;需要在每个时间属性上都要加上该注解&#xff0c;使用较麻烦&#xff0c;不能全局处理。 2). 方式二&#xff08;推荐 ) 在WebMvcConfiguration中扩展SpringMVC的消息转…...

MySQL中的索引失效情况介绍

MySQL中的索引是提高查询性能的重要工具。然而&#xff0c;在某些情况下&#xff0c;索引可能无法发挥作用&#xff0c;甚至导致查询性能下降。在本教程中&#xff0c;我们将探讨MySQL中常见的索引失效情况&#xff0c;以及它们的特点和简单的例子。 1. **索引失效的情况** …...

SpringBoot异常:类文件具有错误的版本 61.0, 应为 52.0的解决办法

问题&#xff1a; java: 无法访问org.mybatis.spring.annotation.MapperScan 错误的类文件: /D:/Program Files/apache-maven-3.6.0/repository/org/mybatis/mybatis-spring/3.0.3/mybatis-spring-3.0.3.jar!/org/mybatis/spring/annotation/MapperScan.class 类文件具有错误的…...

Cloudways搭建WordPress外贸独立站完整教程

现在做个网站不比从前了&#xff0c;搭建网站非常的简单&#xff0c;主要是由于开源的CMS建站系统的崛起&#xff0c;就算不懂编程写代码的人也能搭建一个自己的网站&#xff0c;这些CMS系统提供了丰富的主题模板和插件&#xff0c;使用户可以通过简单的拖放和配置操作来建立自…...

关于 闰年 的小知识,为什么这样判断闰年

闰年的规定&#xff1a; 知道了由来&#xff0c;我们就可以写程序来判断&#xff1a; #include <stdio.h> int main() {int year, leap;scanf("%d",&year);if((year%4 0 && year%100 ! 0) || year%400 0)leap 1;else leap 0;if(leap) printf(…...

Elasticsearch:调整近似 kNN 搜索

在我之前的文章 “Elasticsearch&#xff1a;调整搜索速度”&#xff0c;我详细地描述了如何调整正常的 BM25 的搜索速度。在今天的文章里&#xff0c;我们来进一步探讨如何提高近似 kNN 的搜索速度。希望对广大的向量搜索开发者有一些启示。 Elasticsearch 支持近似 k 最近邻…...

UE5数字孪生系列笔记(二)

智慧城市数字孪生系统 制作流云动画效果 首先添加一个图像在需要添加流云效果的位置 添加动画效果让其旋转 这个动画效果是程序开始就要进行的&#xff0c;所以要在EventConstruct中就可以启动这个动画效果 添加一个一样的图像在这里&#xff0c;效果是从此处进行放大消散 添…...

基于vue实现bilibili网页

学校要求的实验设计,基于vue实现bilibili网页版,可实现以下功能 (1)基本的悬浮动画和页面渲染 (2)可实现登录和未登录的页面变化 (3)在登录页面的,实现密码判断,或者短信验证方式的倒数功能 (4)实现轮播图 (5)实现预览视频(GIF) (6)页面下拉到一定高度出现top栏以及右下角的返回…...

计算机二级(Python)真题讲解每日一题:《十字叉》

描述‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬ ‪‬‪‬‪‬‪‬‪‬‮‬‪…...

基于正点原子潘多拉STM32L496开发板的简易示波器

一、前言 由于需要对ADC采样性能的评估&#xff0c;重点在于对原波形的拟合性能。 考虑到数据的直观性&#xff0c;本来计划采集后使用串口导出&#xff0c;并用图形做数据拟合&#xff0c;但是这样做的效率低下&#xff0c;不符合实时观察的需要&#xff0c;于是将开发板的屏幕…...

【Docker】apisix 容器化部署

APISIX环境标准软件基于Bitnami apisix 构建。当前版本为3.8.0 你可以通过轻云UC部署工具直接安装部署&#xff0c;也可以手动按如下文档操作&#xff0c;该项目已经全面开源&#xff0c;可以从如下环境获取 配置文件地址: https://gitee.com/qingplus/qingcloud-platform qi…...

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的障碍物检测系统(深度学习代码+UI界面+训练数据集)

摘要&#xff1a;开发障碍物检测系统对于道路安全性具有关键作用。本篇博客详细介绍了如何运用深度学习构建一个障碍物检测系统&#xff0c;并提供了完整的实现代码。该系统基于强大的YOLOv8算法&#xff0c;并对比了YOLOv7、YOLOv6、YOLOv5&#xff0c;展示了不同模型间的性能…...

从零开始学HCIA之SDN04

1、VXLAN数据封装 &#xff08;1&#xff09;Original L2 Frame&#xff0c;原始以太网报文&#xff0c;业务应用的以太网帧。 &#xff08;2&#xff09;VXLAN Header&#xff0c;VXLAN协议新定义的VXLAN头&#xff0c;长度为8字节。VXLAN ID&#xff08;VNI&#xff09;为2…...

GET 和 POST 有什么区别?

1.从缓存的角度&#xff0c;GET 请求会被浏览器主动缓存下来&#xff0c;留下历史记录&#xff0c;而 POST 默认不会。 2.从编码的角度&#xff0c;GET 只能进行 URL 编码&#xff0c;只能接收 ASCII 字符&#xff0c;而 POST 没有限制。 3.从参数的角度&#xff0c;GET 一般放…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...