一维坐标的移动(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;

	//向前走,坐标+1
	y=x+1;
	if(!st[y]&&y>=1&&y<=n){
		st[y]=true;
		dfs(y,step+1);
		st[y]=false;
	}
	
	//向后走,坐标-1
	y=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;
} 

 

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

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

相关文章

四.排序(冒泡/选择)

目录 11-排序介绍 常见排序算法: 12-冒泡排序介绍 代码要求: 思路: 13-冒泡排序 代码: 14-选择排序 简单写法: 好的写法: 11-排序介绍 排序&#xff1a;将一组“无序”的记录序列调整为“有序”的记录序列。 列表排序&#xff1a;将无序列表变为有序列表 输入&#…

LeetCode 2312.卖木头块:动态规划(DP)

【LetMeFly】2312.卖木头块&#xff1a;动态规划(DP) 力扣题目链接&#xff1a;https://leetcode.cn/problems/selling-pieces-of-wood/ 给你两个整数 m 和 n &#xff0c;分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices &#xff0c;其中 prices[i] [hi, …

SCI一区 | Matlab实现RIME-TCN-BiGRU-Attention霜冰算法优化时间卷积双向门控循环单元融合注意力机制多变量时间序列预测

SCI一区 | Matlab实现RIME-TCN-BiGRU-Attention霜冰算法优化时间卷积双向门控循环单元融合注意力机制多变量时间序列预测 目录 SCI一区 | Matlab实现RIME-TCN-BiGRU-Attention霜冰算法优化时间卷积双向门控循环单元融合注意力机制多变量时间序列预测预测效果基本介绍模型描述程…

面试经典150题(114-118)

leetcode 150道题 计划花两个月时候刷完之未完成后转&#xff0c;今天完成了5道(114-118)150 gap 了一周&#xff0c;以后就不记录时间了。。 114.(70. 爬楼梯) 题目描述&#xff1a; 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不…

【CTF笔记】 CTF web方向笔记分享 免费 附预览图

个人不怎么记东西&#xff0c;笔记不多&#xff0c;师傅们凑合看… 百度网盘&#xff1a;https://pan.baidu.com/s/1PspihUX28Y_AOQZPurHqKA 麻烦各位师傅帮忙填写一下问卷&#xff0c;提取码在问卷填写结束后显示~ 【https://www.wjx.cn/vm/mBBTTKm.aspx# 】 &#xff08;…

6大赚钱平台大揭秘,正规靠谱,电脑手机均可操作增收

找到一个真正靠谱的赚钱平台&#xff0c;无疑是你开启创收之旅的绝佳起点&#xff01;接下来&#xff0c;我将为你提供一些建议&#xff0c;帮助你在这浩瀚的互联网世界中&#xff0c;稳稳地迈出赚取第一桶金的第一步。 参与调查问卷&#xff1a;像Swagbucks和YouGov这样的调查…

信号量——生产消费者模型

前文 在这一篇博客&#xff08;信号量博客&#xff09;中我曾经提及过信号量的知识&#xff0c;而当对信号量进行提炼总结时&#xff0c;大致是以下三点&#xff1a; 1. 信号量本质是一个计数器&#xff08;代表资源的数量&#xff09; 2. 申请信号量本质就是对资源的一种预定机…

AI大模型额外学习一:斯坦福AI西部世界小镇笔记(包括部署和源码分析)

文章目录 一、简单介绍1&#xff09;项目代码介绍2&#xff09;重新播放模拟3&#xff09;适当修改分叉模拟 二、部署斯坦福小镇Demo1&#xff09;准备工作2&#xff09;解决遇到的bug3&#xff09;启动服务器和前端 三、源码剖析1&#xff09;主题顺序 github链接 一、简单介…

luceda ipkiss教程 62:等长波导布线(二)

教程 27介绍了两段波导等长布线的例子&#xff0c;下面同样是通过控制偏移量实现三段波导的等长布线&#xff1a; 所有代码如下&#xff1a; from si_fab import all as pdk from ipkiss3 import all as i3class demo(i3.Circuit):mmi i3.ChildCellProperty(doc"mmi in…

【面经八股】搜广推方向:面试记录(九)

【面经&八股】搜广推方向:面试记录(九) 文章目录 【面经&八股】搜广推方向:面试记录(九)1. 自我介绍2. 科研-项目经历问答3. 实习经历问答4. 八股5. 编程题6. 反问1. 自我介绍 。。。。。。 2. 科研-项目经历问答 挑了我的论文,一直揪着问,建议一定要熟悉自…

mysql主从复制/主从备份搭建

mysql主从复制/主从备份搭建 前言一、主从复制1&#xff09;为什么使用主从复制、读写分离&#xff1f;2&#xff09;主从复制原理 二、如何实现主从复制&#xff1f;1&#xff09;主库配置1、修改配置文件2、登录mysql&#xff1a; 2&#xff09;从库配置1、修改配置文件2、登…

函数-Python

师从黑马程序员 函数初体验 str1"asdf" str2"qewrew" str3"rtyuio" def my_len(data):count0for i in data:count1print(f"字符串{data}的长度是{count}")my_len(str1) my_len(str2) my_len(str3) 函数的定义 函数的调用 函数名&a…

爱恩斯坦棋小游戏使用C语言+ege/easyx实现

目录 1、游戏介绍和规则 2、需要用到的头文件 3、这里我也配上一个ege和easyx的下载链接吧&#xff0c;应该下一个就可以 4、运行结果部分展示 5、需要用到的图片要放在代码同一文件夹下 6、代码地址&#xff08;里面有需要用到的图片&#xff09; 1、游戏介绍和规则 规则如…

电学基础知识

目录 电流 前言 电流的产生 电流的单位安培&#xff08;A&#xff09; 电路和电池 开路和闭路 电灯泡原理 对电池容量的理解 毫安时 毫瓦时 直流电和交流电 AC交流电 DC直流电 直流电和交流电对比 电压 对电器的电压和电流的理解 电阻 电压电阻电子的关系 欧…

GateWay路由规则

Spring Cloud GateWay 帮我们内置了很多 Predicates功能&#xff0c;实现了各种路由匹配规 则&#xff08;通过 Header、请求参数等作为条件&#xff09;匹配到对应的路由 1 时间点后匹配 server:port: 8888 spring:application:name: gateway-servicecloud:nacos:discovery:…

超实用!免费软件站大盘点,总有一款适合你

相信用Mac电脑的同学都知道一个网站MacWK&#xff0c;可以白嫖几乎所有常用软件&#xff0c;不用付费&#xff0c;但不好的消息是在2022年10月宣布关站&#xff0c;小编从此走上了开源免费的道路&#xff0c;尽管不太好用&#xff0c;奈何口袋木有钱&#xff0c;经过小编的不断…

VS2022 配置QT5.9.9

QT安装 下载地址&#xff1a;https://download.qt.io/archive/qt/ 下载安装后进行配置 无法运行 rc.exe 下载VS2022 官网下载 配置 1.扩展-管理扩展-下载Qt Visual Studio Tools 安装 2.安装完成后&#xff0c;打开vs2022,点击扩展&#xff0c;会发现多出了QT VS Tools,点…

【学习学习】学习金字塔

学习金字塔&#xff08;Cone of Learning&#xff09;&#xff0c;全称学习吸收率金字塔&#xff0c;是一种现代学习方式的理论。网上流传它是美国缅因州的国家训练实验室&#xff08;National Training Laboratories&#xff09;研究成果&#xff0c;用数字形式形象显示了采用…

数据分析-Pandas序列时间移动窗口化操作

数据分析-Pandas序列时间移动窗口化操作 数据分析和处理中&#xff0c;难免会遇到各种数据&#xff0c;那么数据呈现怎样的规律呢&#xff1f;不管金融数据&#xff0c;风控数据&#xff0c;营销数据等等&#xff0c;莫不如此。如何通过图示展示数据的规律&#xff1f; 数据表…

Elasticsearch:调整近似 kNN 搜索

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