每天一道leetcode:剑指 Offer 13. 机器人的运动范围(中等广度优先遍历剪枝)
今日份题目:
地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?
示例1
输入:m = 2, n = 3, k = 1 输出:3
示例2
输入:m = 3, n = 1, k = 0 输出:1
提示
-
1 <= n,m <= 100 -
0 <= k <= 20
题目思路
由于机器人是从(0,0)开始走,并不一定能走过所有格子,甚至不一定能走到右下角,所以其实是个搜索过程,故使用广度优先遍历,将满足条件(坐标在格子内且位数和小于k)的点坐标放入队列,每次从队列中取出第一个点坐标判断向下向右两个点左边,然后继续,直到队列不为空。剪枝,只考虑向下向右两个方向即可,这是由本题规律得出的,随着k的增大,可行区域都是增加在右和下两个方向的:



补充:方向

代码
class Solution
{
public:int num(int x) //计算x的数位之和{string s=to_string(x);//将int型数据转换成字符串类型int res=0;for(int i=0;i<s.length();i++) {res+=s[i]-'0';//计算各位之和}return res;}int movingCount(int m, int n, int k) {if(k==0) return 1;queue<pair<int,int> > p;//向右和向下的方向数组int dx[2]={0,1};int dy[2]={1,0};int visited[200][200]={0};//用于标记是否到达过//从(0,0)开始p.push({0,0});visited[0][0]=1;int ans=1;//bfs广度优先遍历while(!p.empty()) {pair<int,int> xy=p.front();p.pop();for(int i=0;i<2;i++) //遍历两个方向{int tx=dx[i]+xy.first;int ty=dy[i]+xy.second;if(tx<0||tx>=m||ty<0||ty>=n||visited[tx][ty]==1||num(tx)+num(ty)>k) continue;//避免到方格外、被遍历过、数位之和大于kp.push({tx,ty});visited[tx][ty]=1;ans++;}}return ans;}
};
提交结果

欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!
相关文章:
每天一道leetcode:剑指 Offer 13. 机器人的运动范围(中等广度优先遍历剪枝)
今日份题目: 地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之…...
TypeError: a bytes-like object is required, not ‘str‘
raceback (most recent call last): File "D:\pycharmcode\client.py", line 12, in <module> tcp_socket.send(send_data) TypeError: a bytes-like object is required, not str 使用socket进行ubuntu与windows通信时,发送数据时报了以上错…...
题解 | #1005.List Reshape# 2023杭电暑期多校9
1005.List Reshape 签到题 题目大意 按一定格式给定一个纯数字一维数组,按给定格式输出成二维数组。 解题思路 读入初始数组字符串,将每个数字分离,按要求输出即可 参考代码 参考代码为已AC代码主干,其中部分功能需读者自行…...
会声会影2023旗舰版电脑端视频剪辑软件
随着短视频、vlog等媒体形式的兴起,视频剪辑已经成为了热门技能。甚至有人说,不会修图可以,但不能不会剪视频。实际上,随着各种智能软件的发展,视频剪辑已经变得越来越简单。功能最全的2023新版,全新视差转…...
【linux基础(四)】对Linux权限的理解
💓博主CSDN主页:杭电码农-NEO💓 ⏩专栏分类:Linux从入门到开通⏪ 🚚代码仓库:NEO的学习日记🚚 🌹关注我🫵带你学更多操作系统知识 🔝🔝 Linux权限 1. 前言2. shell命…...
maven项目指定数据源
springboot项目 直接在pom.xml文件中添加以下配置 <!--使用阿里云maven中央仓库--> <repositories><repository><id>aliyun-repos</id><url>http://maven.aliyun.com/nexus/content/groups/public/</url><snapshots><ena…...
web3:使用Docker-compose方式部署blockscout
最近做的项目,需要blockscout来部署一个区块链浏览器,至于blockscout是什么,咱们稍后出一篇文章专门介绍下,本次就先介绍一下如何使用Docker-compose方式部署blockscout,以及过程中遇到的种种坑 目录 先决条件我的环境准备工作Docker-compose1.安装方式一:下载 Docker Co…...
C++11实用技术(五)泛型编程加载dll接口函数
C11泛型编程简化加载dll代码 常见的加载dll方式: HMODULE m_hDataModule; m_hDataModule LoadLibrary("myDll.dll");typedef int (*PfunA)(int a, int b);//定义函数指针 PfunA fun (PfunA)(GetProcAddress(m_hDataModule , "funA"));//加载…...
使用wxPython和PyMuPDF提取PDF页面指定页数的内容的应用程序
在本篇博客中,我们将探讨如何使用wxPython和PyMuPDF库创建一个简单的Bokeh应用程序,用于选择PDF文件并提取指定页面的内容,并将提取的内容显示在文本框中。 C:\pythoncode\new\pdfgetcontent.py 准备工作 首先,确保你已经安装了…...
k8s的pv和pvc创建
//NFS使用PV和PVC 1、配置nfs存储 2、定义PV 实现 下图的pv和pvc测试 pv的定义 这里定义5个PV,并且定义挂载的路径以及访问模式,还有PV划分的大小 vim /pv.yamlapiVersion: v1 kind: PersistentVolume metadata:name: pv001 spec:capacity:storage: …...
记K8S集群工作节点,AnolisOS 8.6部署显卡驱动集成Containerd运行时
1、安装gcc #安装编译环境 yum -y install make gcc gcc-c2、下载显卡驱动 点击 直达连接 nvidia高级搜索下载历史版本驱动程序(下载历史版本驱动) https://www.nvidia.cn/Download/Find.aspx?langcn3、安装驱动 安装显卡驱动 ./NVIDIA-Linux-x86…...
JavaScript 性能优化
优化JavaScript代码的性能是开发过程中的一个关键任务,它可以显著提升网站或应用的用户体验。以下是一些优化技巧,涵盖了减少重绘、减少内存占用和合并网络请求等方面: 1. **减少重绘和重排:** - **使用 CSS3 动画:…...
架构演进及常用架构
1架构演进及常用架构 1.1单体分层架构 1.2 多应用微服务架构 1.3 分布式集群部署 部署 CDN 节点: 用户访问量的增加意味着用户地域的分散请求,如果所有请求都直接发送中心服务器的话,距离越远,响应速度越差,这时就需…...
WinCC V7.5 中的C脚本对话框不可见,将编辑窗口移动到可见区域的具体方法
WinCC V7.5 中的C脚本对话框不可见,将编辑窗口移动到可见区域的具体方法 由于 Windows 系统更新或使用不同的显示器,在配置C动作时,有可能会出现C脚本编辑窗口被移动到不可见区域的现象。 由于该窗口无法被关闭,故无法进行进一步…...
【实战】十一、看板页面及任务组页面开发(二) —— React17+React Hook+TS4 最佳实践,仿 Jira 企业级项目(二十四)
文章目录 一、项目起航:项目初始化与配置二、React 与 Hook 应用:实现项目列表三、TS 应用:JS神助攻 - 强类型四、JWT、用户认证与异步请求五、CSS 其实很简单 - 用 CSS-in-JS 添加样式六、用户体验优化 - 加载中和错误状态处理七、Hook&…...
Vue2.7.14、vuecli@5.0.8 升级 vite@4.4.8
项目背景 Vue2.7.14、vuecli5.0.8、element-ui2.15.13、node14.18.3 vite安装 pnpm add vite4.4.8 -D 入口文件index.html 文件位置修改 将pulic里的index.html移到根目录下 根目录/public/index.html 到 根目录/index.html 文件内容修改 <link rel"icon"…...
LeetCode[面试题04.12]求和路径
难度:Medium 题目: 给定一棵二叉树,其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法,打印节点数值总和等于某个给定值的所有路径的数量。注意,路径不一定非得从二叉树的根节点或叶节点开始或结束&#x…...
骑行运动耳机哪款好?五年骑行爱好者给你分享分享
作为一名骑行达人,我尝试过多种骑行耳机,有入耳式、耳罩式、骨传导等等,但总有一款让我特别满意。直到我遇到了这几款耳机,它不仅音质出色,而且非常适合骑行,让我爱不释手。下面,我将分享一下这…...
SpringBoot3集成ElasticSearch
标签:ElasticSearch8.Kibana8; 一、简介 Elasticsearch是一个分布式、RESTful风格的搜索和数据分析引擎,适用于各种数据类型,数字、文本、地理位置、结构化数据、非结构化数据; 在实际的工作中,历经过Ela…...
详解23种设计模式优缺点以及解决方案
1. 单例模式(Singleton Pattern): 优点:确保一个类只有一个实例,提供全局访问点,节省资源。缺点:可能引入全局状态,难以扩展和测试。解决方法:使用依赖注入来替代直接访…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
