机器人运动范围检测 c++
地上有一个m行n列的方格,一个机器人从坐标(0,0)的格子开始移动,它每次可以向上下左右移动一个格子,但不能进入行坐标和列坐标的位数之和大于k的格子,请问机器人能够到达多少个格子
#include <vector> // 包含vector头文件
#include <queue> // 包含queue头文件class Solution { // 定义解决方案类
private:int getSum(int x, int y) { // 计算坐标数位之和int sum = 0; // 初始化和为0while (x > 0) { // 处理x坐标sum += x % 10; // 加上个位数x /= 10; // 去掉个位数}while (y > 0) { // 处理y坐标sum += y % 10; // 加上个位数y /= 10; // 去掉个位数}return sum; // 返回数位之和}public:int movingCount(int m, int n, int k) { // 计算可到达的格子数if (k < 0) return 0; // 如果k小于0,无法移动std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false)); // 记录已访问的格子std::queue<std::pair<int, int>> q; // 用于BFS的队列int count = 0; // 可到达的格子数q.push({0, 0}); // 起始点加入队列visited[0][0] = true; // 标记起始点为已访问int dx[4] = {-1, 1, 0, 0}; // x方向的移动int dy[4] = {0, 0, -1, 1}; // y方向的移动while (!q.empty()) { // BFS主循环auto [x, y] = q.front(); // 获取当前格子坐标q.pop(); // 从队列中移除count++; // 增加可到达的格子数for (int i = 0; i < 4; i++) { // 尝试四个方向的移动int nx = x + dx[i], ny = y + dy[i]; // 计算新坐标if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && getSum(nx, ny) <= k) { // 检查新坐标是否有效q.push({nx, ny}); // 将新坐标加入队列visited[nx][ny] = true; // 标记新坐标为已访问}}}return count; // 返回可到达的格子数}
};
这个实现使用了广度优先搜索(BFS)算法来解决问题。以下是主要的设计思路:
- 我们定义了一个
Solution
类,其中包含两个主要函数:getSum
: 这是一个私有辅助函数,用于计算坐标的数位之和。movingCount
: 这是公共接口函数,用于计算机器人能够到达的格子数量。
- 在
movingCount
函数中:- 我们使用一个二维布尔数组
visited
来记录已经访问过的格子。 - 使用一个队列
q
来进行BFS。 - 从(0,0)开始,将其加入队列并标记为已访问。
- 使用一个while循环进行BFS,每次从队列中取出一个格子,然后尝试向四个方向移动。
- 对于每个新的可能位置,我们检查:
- 是否在网格范围内
- 是否已经被访问过
- 数位之和是否不大于k
- 如果满足所有条件,我们将新位置加入队列,并标记为已访问。
- 每访问一个新的格子,我们就将计数器加1。
- 我们使用一个二维布尔数组
- 最后返回计数器的值,即为机器人能够到达的格子数量。
这个算法的时间复杂度为O(mn),其中m和n分别是网格的行数和列数。空间复杂度也是O(mn),主要用于存储visited数组和BFS队列。
相关文章:
机器人运动范围检测 c++
地上有一个m行n列的方格,一个机器人从坐标(0,0)的格子开始移动,它每次可以向上下左右移动一个格子,但不能进入行坐标和列坐标的位数之和大于k的格子,请问机器人能够到达多少个格子 #include &l…...
kettle从入门到精通 第七十四课 ETL之kettle kettle调用https接口教程,忽略SSL校验
场景:kettle调用https接口,跳过校验SSL。(有些公司内部系统之间的https的接口是没有SSL校验这一说,无需使用用证书的) 解决方案:自定义插件或者自定义jar包通过javascript调用https接口。 1、http post 步…...
C++轻量级 线程间异步消息架构(向曾经工作的ROSA-RB以及共事的DOPRA的老兄弟们致敬)
1 啰嗦一番背景 这么多年,换着槽位做牛做马,没有什么钱途 手艺仍然很潮,唯有对于第一线的码农工作,孜孜不倦,其实没有啥进步,就是在不断地重复,刷熟练度,和同期的老兄弟们…...
Kotlin中的类
类初始化顺序 constructor 里的参数列表是首先被执行的,紧接着是 init 块和属性初始化器,最后是次构造函数的函数体。 主构造函数参数列表firstProperty 初始化第一个 init 块secondProperty 初始化第二个 init 块次构造函数函数体 class Example const…...
VSCode中常用的快捷键
通用操作快捷键 显示命令面板:Ctrl Shift P or F1,用于快速访问VSCode的各种命令。 快速打开:Ctrl P,可以快速打开文件、跳转到某个行号或搜索项目内容。 新建窗口/实例:Ctrl Shift N,用于打开一个新的…...
代码随想录-Day45
198. 打家劫舍 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个…...
Rust Eq 和 PartialEq
Eq 和 PartialEq 在 Rust 中,想要重载操作符,你就需要实现对应的特征。 例如 <、<、> 和 > 需要实现 PartialOrd 特征: use std::fmt::Display;struct Pair<T> {x: T,y: T, }impl<T> Pair<T> {fn new(x: T, y: T) ->…...
思考如何学习一门编程语言?
一、什么是编程语言 编程语言是一种用于编写计算机程序的人工语言。通过编程语言,程序员可以向计算机发出指令,控制计算机执行各种任务和操作。编程语言由一组语法规则和语义规则组成,这些规则定义了如何编写代码以及代码的含义。 编程语言…...
顺序串算法库构建
学习贺利坚老师顺序串算法库 数据结构之自建算法库——顺序串_创建顺序串s1,创建顺序串s2-CSDN博客 本人详细解析博客 串的概念及操作_串的基本操作-CSDN博客 版本更新日志 V1.0: 在贺利坚老师算法库指导下, 结合本人详细解析博客思路基础上,进行测试, 加入异常弹出信息 v1.0补…...
[论文阅读笔记33] Matching Anything by Segmenting Anything (CVPR2024 highlight)
这篇文章借助SAM模型强大的泛化性,在任意域上进行任意的多目标跟踪,而无需任何额外的标注。 其核心思想就是在训练的过程中,利用strong augmentation对一张图片进行变换,然后用SAM分割出其中的对象,因此可以找到一组图…...
阿里Nacos下载、安装(保姆篇)
文章目录 Nacos下载版本选择Nacos安装Windows常见问题解决 更多相关内容可查看 Nacos下载 Nacos官方下载地址:https://github.com/alibaba/nacos/releases 码云拉取(如果国外较慢或者拉取超时可以试一下国内地址) //国外 git clone https:…...
四、golang基础之defer
文章目录 一、定义二、作用三、结果四、recover错误拦截 一、定义 defer语句被用于预定对一个函数的调用。可以把这类被defer语句调用的函数称为延迟函数。 二、作用 释放占用的资源捕捉处理异常输出日志 三、结果 如果一个函数中有多个defer语句,它们会以LIFO…...
机器人----四元素
四元素 四元素的大小 [-1,1] 欧拉角转四元素...
IBM Spectrum LSF Application Center 提供单一界面来管理应用程序、用户、资源和数据
IBM Spectrum LSF Application Center 提供单一界面来管理应用程序、用户、资源和数据 亮点 ● 简化应用程序管理 ● 提高您的工作效率 ● 降低资源管理的复杂性 ● 深入了解流程 IBM Spectrum LSF Application Center 为集群用户和管理员提供了一个灵活的、以应用为中心的界…...
如何选择品牌推广公司?哪家好?收费标准及评价!
不管是什么品牌,推广对公司的成败起了很关键的作用。然而,面对市面上琳琅满目的品牌推广公司,如何选择一家既熟悉又靠谱的公司,成为许多企业主面临的难题。 作为一家手工酸奶品牌的创始人,目前全国也复制了100多家门店…...
JDeveloper 12C 官网下载教程
首先、我们要登录Oracle官网 Oracle 甲骨文中国 | 云应用和云平台 登录进去如果不是中文可以点击右上角带有国旗的图标就行更改,选择一个你能看懂的文字。 然后,点击“资源”—点击“开发人员下载” 然后,点击“开发工具” 这里有很多工具可…...
中英双语介绍美国的州:印第安纳州(Indiana)
中文版 印第安纳州简介 印第安纳州位于美国中西部地区,是一个以其农业、制造业和体育文化而著称的州。以下是对印第安纳州的详细介绍,包括其地理位置、人口、经济、教育、文化和主要城市。 地理位置 印第安纳州东临俄亥俄州,北接密歇根州…...
Flink实现准确和高效流处理的关键问题
时间相关: Watermark 水位线 水位线是插入到数据流中的一个标记,可以认为是一个特殊的数据。水位线主要的内容是一个时间戳,用来表示当前事件时间的进展。水位线是基于数据的时间戳生成的。水位线的时间戳必须单调递增,以确保任务的事件时间时钟一直向前推进,进展。水位线…...
isidentifier()方法——判断字符串是否为合法的Python标识符或变量名
自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 语法参考 isidentifier()方法用于判断字符串是否是有效的Python标识符,还可以用来判断变量名是否合法。isidentifier()方法的语法格式如…...
天猫商品列表数据接口(Tmall.item_search)
天猫平台商品列表数据接口(taobao.item_search)是天猫开放平台提供的一个API接口,用于获取天猫平台上的商品列表数据。通过该接口,用户可以获取到商品的名称、价格、销量、评价等信息。下面将具体介绍这个接口的各个方面ÿ…...
React+TS前台项目实战(二十一)-- Search业务组件封装实现全局搜索
文章目录 前言一、Search组件封装1. 效果展示2. 功能分析3. 代码详细注释4. 使用方式 二、搜索结果展示组件封装1. 功能分析2. 代码详细注释 三、引用到文件,自行取用总结 前言 今天,我们来封装一个业务灵巧的组件,它集成了全局搜索和展示搜…...
SEO与AI的结合:如何用ChatGPT生成符合搜索引擎优化的内容
在当今数字时代,搜索引擎优化(SEO)已成为每个网站和内容创作者都必须掌握的一项技能。SEO的主要目标是通过优化内容,使其在搜索引擎结果页面(SERP)中排名更高,从而吸引更多的流量。然而…...
【信息系统项目管理师知识点速记】组织通用管理:知识管理
23.3 知识管理 23.3.1 知识管理基础 知识管理是通过利用各种知识和技术手段,帮助组织和个人生产、分享、应用和创新知识,以形成知识优势并在个人、组织、业务目标、经济绩效和社会效益方面产生价值的过程。它能为组织带来知识增值,创造新的价值,提升决策效能和水平,是提…...
CM-UNet: Hybrid CNN-Mamba UNet for Remote Sensing Image Semantic Segmentation
论文:CM-UNet: Hybrid :CNN-Mamba UNet for Remote Sensing Image Semantic Segmentation 代码:https://github.com/XiaoBuL/CM-UNet Abstrcat: 由于大规模图像尺寸和对象变化,当前基于 CNN 和 Transformer 的遥感图像语义分割方…...
DP:子序列问题
文章目录 什么是子序列子序列的特点举例说明常见问题 关于子序列问题的几个例题1.最长递增子序列2.摆动序列3.最长递增子序列的个数4.最长数对链5.最长定差子序列 总结 什么是子序列 在计算机科学和数学中,子序列(Subsequence)是指从一个序列…...
Spring Data与多数据源配置
Spring Data与多数据源配置 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!今天我们来探讨如何在Spring Data中配置和使用多个数据源。 在现代应用程序中&…...
【前端vue3】TypeScrip-类型推论和类型别名
类型推论 TypeScript里,在有些没有明确指出类型的地方,类型推论会帮助提供类型。 例如: 变量xiaoc被推断类型为string 如重新给xiaoc赋值数字会报错 let xiaoc "xiaoc"xiaoc 1111111111111如没有给变量指定类型和赋值…...
javaEE——Servlet
1.web开发概述 所谓web开发,指的是从网页中向后端程序发送请求,与后端程序进行交互 2.java后端开发环境搭建 web后端(javaEE)程序需要运行在服务器中的,这样前端才可以访问得到 3.服务器是什么? ①服务器就是一款软件,可以向其发送请求&#…...
Kotlin扩展函数(also apply run let)和with函数
also apply run let with的使用例子 private fun testOperator() {/*** also*/val person Person("ZhangSan", 18)person.also {// 通常仅仅打印使用, 也可以通过it修改it.name "ZhangSan1"println("also inner name: " it.name)}println(&qu…...
C语言笔记27 •单链表介绍•
1.链表的概念及结构 链表是⼀种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表 中的指针链接次序实现的。 2. 顺序表带来的问题 (1)中间/头部的插⼊删除,时间复杂度为O(N) (2)增容需要申请新空间,拷⻉数据ÿ…...
C++编程(五)单例模式 友元
文章目录 一、单例模式(一)概念(二)实现方式1. 饿汉式2. 懒汉式 二、友元(一)概念(二)友元函数1.概念2.语法格式3. 使用示例访问静态成员变量访问非静态成员变量 (三&…...
012-GeoGebra基础篇-构造圆的切线
前边文章对于基础内容已经悉数覆盖了,这一篇我就不放具体的细节,若有需要可以复刻一下 目录 一、成品展示二、算式内容三、正确性检查五、文章最后 一、成品展示 二、算式内容 A(0,0) B(3,0) c: Circle(A,B) C(5,4) sSegment(A,C) DMidpoint(s) d: Circ…...
数据结构速成--查找
由于是速成专题,因此内容不会十分全面,只会涵盖考试重点,各学校课程要求不同 ,大家可以按照考纲复习,不全面的内容,可以看一下小编主页数据结构初阶的内容,找到对应专题详细学习一下。 目录 …...
SpringMVC的基本使用
SpringMVC简介 SpringMVC是Spring提供的一套建立在Servlet基础上,基于MVC模式的web解决方案 SpringMVC核心组件 DispatcherServlet:前置控制器,来自客户端的所有请求都经由DispatcherServlet进行处理和分发Handler:处理器&…...
【PYG】Cora数据集分类任务计算损失,cross_entropy为什么不能直接替换成mse_loss
cross_entropy计算误差方式,输入向量z为[1,2,3],预测y为[1],选择数为2,计算出一大坨e的式子为3.405,再用-23.405计算得到1.405MSE计算误差方式,输入z为[1,2,3],预测向量应该是[1,0,0]࿰…...
MyBatis-plus这么好用,不允许还有人不会
你好呀,我是 javapub. 做 Java 的同学都会用到的三件套,Spring、SpringMV、MyBatis。但是由于使用起来配置较多,依赖冲突频发。所有,各路大佬又在这上边做了包装,像我们常用的 SpringBoot、MyBatisPlus。 基于当前要…...
Linux驱动开发实战宝典:设备模型、模块编程、I2C/SPI/USB外设精讲
摘要: 本文将带你走进 Linux 驱动开发的世界,从设备驱动模型、内核模块开发基础开始,逐步深入 I2C、SPI、USB 等常用外设的驱动编写,结合实际案例,助你掌握 Linux 驱动开发技能。 关键词: Linux 驱动,设备驱动模型,内核模块,I2C,SPI,USB 一、Linux 设备驱动模型 Li…...
安全技术和防火墙
1、安全技术 1.1入侵检测系统 特点是不阻断网络访问,主要提供报警和事后监督。不主动介入,默默的看着你(类似于监控) 1.2入侵防御系统 透明模式工作, 数据包,网络监控,服务攻击,…...
Webpack: 开发 PWA、Node、Electron 应用
概述 毋庸置疑,对前端开发者而言,当下正是一个日升月恒的美好时代!在久远的过去,Web 页面的开发技术链条非常原始而粗糙,那时候的 JavaScript 更多用来点缀 Web 页面交互而不是用来构建一个完整的应用。直到 2009年5月…...
python处理txt文件, 如果第一列和第二列的值在连续的行中重复,则只保留一行
处理txt文件, 如果第一列和第二列的值在连续的行中重复,则只保留一个实例,使用Python的内置函数来读取文件,并逐行检查和处理数据。 一个txt文件,里面的数据是893.554382324,-119.955825806,0.0299997832626,-0.133618548512,28.1155740884,112.876833236,46.7922,19.62582…...
C++17中引入了什么新的重要特性
C17是C标准的一个重要版本,它在语言核心和标准库中引入了许多新特性和改进,使得C编程更加现代化和高效。以下是C17中引入的一些重要新特性: 语言核心新特性 结构化绑定(Structured Bindings): 结构化绑定…...
Andrej Karpathy提出未来计算机2.0构想: 完全由神经网络驱动!网友炸锅了
昨天凌晨,知名人工智能专家、OpenAI的联合创始人Andrej Karpathy提出了一个革命性的未来计算机的构想:完全由神经网络驱动的计算机,不再依赖传统的软件代码。 嗯,这是什么意思?全部原生LLM硬件设备的意思吗?…...
用国内镜像安装docker 和 docker-compose (ubuntu)
替代方案,改用国内的镜像站(网易镜像) 1.清除旧版本(可选操作) for pkg in docker.io docker-doc docker-compose podman-docker containerd runc; do apt-get remove $pkg; done 2.安装docker apt-get update 首先安装依赖 apt-g…...
Linux多线程【线程互斥】
文章目录 Linux线程互斥进程线程间的互斥相关背景概念互斥量mutex模拟抢票代码 互斥量的接口初始化互斥量销毁互斥量互斥量加锁和解锁改进模拟抢票代码(加锁)小结对锁封装 lockGuard.hpp 互斥量实现原理探究可重入VS线程安全概念常见的线程不安全的情况常…...
os实训课程模拟考试(大题复习)
目录 一、Linux操作系统 (1)第1关:Linux初体验 (2)第2关:Linux常用命令 (3)第3关:Linux 查询命令帮助语句 二、Linux之进程管理—(重点) &…...
QT/QML国际化:中英文界面切换显示(cmake方式使用)
目录 前言 实现步骤 1. 准备翻译文件 2. 翻译字符串 3.设置应用程序语言 cmake 构建方式 示例代码 总结 1. 使用 file(GLOB ...) 2. 引入其他资源文件 再次生成翻译文件 5. 手动更新和生成.qm文件 其他资源 前言 在当今全球化的软件开发环境中,应用程…...
设计模式在Java项目中的实际应用
设计模式在Java项目中的实际应用 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 引言 设计模式是软件开发中重要的思想工具,它提供了解决特定问题…...
js制作随机四位数验证码图片
<div class"lable lable2"><div class"l"><span>*</span>验证码</div><div class"r"><input type"number" name"vercode" placeholder"请输入验证码"></div>&l…...
[开源软件] 支持链接汇总
“Common rules: 1- If the repo is on github, the support/bug link is also on the github with issues”" label; 2- Could ask questions by email list;" 3rd party software support link Note gcc https://gcc.gnu.org openssh https://bugzilla.mindrot.o…...
从零开始搭建spring boot多模块项目
一、搭建父级模块 1、打开idea,选择file–new–project 2、选择Spring Initializr,选择相关java版本,点击“Next” 3、填写父级模块信息 选择/填写group、artifact、type、language、packaging(后面需要修改)、java version(后面需要修改成和第2步中版本一致)。点击“…...