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

迷路的机器人(递归回溯+动态规划两个方法实现)

题目:

设想有个机器人坐在一个网格的左上角,网格 r 行 c 列。机器人只能向下或向右移动,但不能走到一些被禁止的网格(有障碍物)。设计一种算法,寻找机器人从左上角移动到右下角的路径。

示例:

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]
解释: 
输入中标粗的位置即为输出表示的路径,即
0行0列(左上角) -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列(右下角)

解题思路:动态规划 

1.先找到可行的路径,不可达的坐标点 dp=0

2.如果终点的dp不为0,说明存在可达的路径

3.那么就从终点往回走,找到可以到达起点的路径,每走一步都要将坐标添加到res数组中

4.由于是从后往前的,所以要将res进行反转

源代码如下:

class Solution {
public:vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {vector<vector<int>> res;if(obstacleGrid.size()==0) return res;//矩阵为空,直接返回空数组int m=obstacleGrid.size();int n=obstacleGrid[0].size();//矩阵的起点和终点不可达,则返回空数组if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1) return res;int dp[m][n];//定义动态规划数组dp[0][0]=1;//起点位置可达,置为1//先找第一列的元素是否可达for(int i=1;i<m;i++){//不可达,dp置为0if(obstacleGrid[i][0]==1) dp[i][0]=0;//可达,则dp等于上一行的else{dp[i][0]=dp[i-1][0];}}//找第一行的元素for(int i=1;i<n;i++){if(obstacleGrid[0][i]==1) dp[0][i]=0;else{dp[0][i]=dp[0][i-1];}}//其他剩余元素for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j]==1) dp[i][j]=0;else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}//如果终点的dp=0,说明不能到达终点,则返回空数组if(dp[m-1][n-1]==0) return res;//以下情况是已经找到路径了,只需要把路径添加到res中//从后往前找可以到达的点int i=m-1,j=n-1;while(i!=0||j!=0){res.push_back({i,j});//往上走int up=0;if(i>0) up=dp[i-1][j];//往左走int left=0;if(j>0) left=dp[i][j-1];//哪个dp值不为0,则走哪个方向if(up>=left) i--;else j--;}//最后把起点添加到数组中res.push_back({0,0});//再将数组翻转,就是正确顺序了reverse(res.begin(),res.end());return res;}
};

 解题思路:回溯

需要注意的是,要添加一个访问数组,标记该坐标是否已经被访问过。详解看代码

源代码如下:

class Solution {
public:bool isfind=false;//是否已经找到路径void dfs(vector<vector<int>>& obstacleGrid,vector<vector<int>>& res,vector<vector<bool>>& visited,int m,int n,int i,int j){//如果下标i和j越界//如果已经找到路径(isfind==true)//如果当前坐标有障碍物//如果当前坐标已访问//遇到以上这些情况 直接返回if(i<0||i>=m||j<0||j>=n||isfind||obstacleGrid[i][j]==1||visited[i][j]) return;//当前坐标已经到达终点,说明找到路径了if(i==m-1&&j==n-1){isfind=true;//isfind置为真res.push_back({i,j});//将终点添加到数组中//并返回return;}//其余正常情况,每遍历一个坐标,就将该坐标标记为已访问visited[i][j]=true;res.push_back({i,j});//坐标添加到数组中//递归,往下走dfs(obstacleGrid,res,visited,m,n,i+1,j);//递归,往右走dfs(obstacleGrid,res,visited,m,n,i,j+1);//回溯if(!isfind) res.pop_back();}vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {vector<vector<int>> res;int m=obstacleGrid.size();int n=obstacleGrid[0].size();if(obstacleGrid.size()==0) return res;//标记当前坐标是否已经访问过,初始值都为falsevector<vector<bool>> visited(m, vector<bool>(n, false));if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1) return res;dfs(obstacleGrid,res,visited,m,n,0,0);return res;}
};

相关文章:

迷路的机器人(递归回溯+动态规划两个方法实现)

题目&#xff1a; 设想有个机器人坐在一个网格的左上角&#xff0c;网格 r 行 c 列。机器人只能向下或向右移动&#xff0c;但不能走到一些被禁止的网格&#xff08;有障碍物&#xff09;。设计一种算法&#xff0c;寻找机器人从左上角移动到右下角的路径。 示例&#xff1a;…...

Nacos

Nacos介绍 Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service的⾸字⺟简称&#xff0c;⼀个更易于构 建云原⽣应⽤的动态服务发现、配置管理和服务管理平台。 在这个介绍中&#xff0c;可以看出Nacos⾄少有三个核⼼功能&#xff1a; 1. 动态服务发现 2. 配…...

【Linux】网络层协议:IP

我们必须接受批评&#xff0c;因为它可以帮助我们走出自恋的幻象&#xff0c;不至于长久在道德和智识上自我陶醉&#xff0c;在自恋中走向毁灭&#xff0c;事实上我们远比自己想象的更伪善和幽暗。 文章目录 一、IP和TCP之间的关系&#xff08;提供策略 和 提供能力&#xff09…...

神经网络为什么可以学习

本资料转载于B站up主&#xff1a;大模型成长之路,仅用于学习和讨论&#xff0c;如有侵权请联系 动画解析神经网络为什么可以学习_哔哩哔哩_bilibilis 1、一个神经网络是由很多神经元形成的 1.1 也可以是一层&#xff0c;也可以是多层 2 层和层之间的连接就跟一张网一样 2.1 每…...

Docker基础入门:镜像、容器导入导出与私有仓库搭建

Docker基础入门&#xff1a;镜像导入导出与私有仓库搭建 一、 Docker镜像、容器的导入和导出1.1、Docker镜像的导出1.2、Docker镜像的载入1.3、Docker容器的导出1.4、Docker容器的导入 二、 镜像和容器导出和导入的区别:三、commit操作_本地镜像发布到阿里云3.1、commit操作有关…...

Go语言入门指南:基础语法和常用特性解析(上)

一、Go语言前言 Go是一种静态类型的编译语言&#xff0c;常常被称作是21世纪的C语言。Go语言是一个开源项目&#xff0c;可以免费获取编译器、库、配套工具的源代码&#xff0c;也是高性能服务器和应用程序的热门选择。 Go语言可以运行在类UNIX系统——比如Linux、OpenBSD、M…...

排序算法合集

F B I W a r n i n g : \color{red}FBI \qquad Warning: FBIWarning: 本人没有完整的计算机科班的教育经历&#xff0c;但是一直在兢兢业业&#xff0c;努力学习。 这些排序函数都是自己零零散散写的&#xff0c;也没有经过深思熟虑和优化&#xff0c;纯粹是为了自娱自乐。 …...

Vue2-全局事件总线、消息的订阅与发布、TodoList的编辑功能、$nextTick、动画与过渡

&#x1f954;&#xff1a;高度自律即自由 更多Vue知识请点击——Vue.js VUE2-Day9 全局事件总线1、安装全局事件总线2、使用事件总线&#xff08;1&#xff09;接收数据&#xff08;2&#xff09;提供数据&#xff08;3&#xff09;组件销毁前最好解绑 3、TodoList中的孙传父&…...

DP读书:鲲鹏处理器 架构与编程(八)3.1鲲鹏处理器片上系统与Taishan处理器内核架构

鲲鹏处理器片上系统架构 一、鲲鹏处理器片上系统与Taishan处理器内核架构1. 鲲鹏处理器片上系统概况a. 鲲鹏处理器片上系统与鲲鹏芯片家族b. 鲲鹏920处理器片上系统的组成部件c. 鲲鹏920处理器片上系统的特征d. 鲲鹏920处理器片上系统的逻辑结构 2. Taishan V110 处理器内核微架…...

如何使用 HOOPS Exchange SDK 和 Polygonica Bridge

这里将讨论使用 HOOPS Exchange 和 Polygonica 以及它们之间的桥梁进行 CAD 访问和网格处理。--提供Crack HOOPS 全系列SDK HOOPS Exchange 基础知识 首先&#xff0c;让我们简单回顾一下 HOOPS Exchange。HOOPS Exchange 是一款具有 C 接口的数据访问 SDK&#xff0c;支持导入…...

spring异步框架使用教程

背景 在需求开发过程中&#xff0c;为了提升效率&#xff0c;很容易就会遇到需要使用多线程的场景。这个时候一般都会选择建一个线程池去专门用来进行某一类动作&#xff0c;这种任务到来的时候往往伴随着大量的线程被创建调用。而还有另外一种场景是整个任务的执行耗时比较长…...

【数学建模】清风数模正课3 插值算法

插值算法 在数模比赛中&#xff0c;很多类型的题目都需要根据已知的函数点进行数据分析和模型处理&#xff1b; 当此时题目所给的数据较少时&#xff0c;我们就无法进行准确科学的分析&#xff0c;所以需要更多的数据&#xff0c;也就是函数点&#xff1b; 这就需要使用数学…...

什么是eval()?eval是用来干什么的?

一、什么是eval()? eval() 是 JavaScript 中的一个全局函数&#xff0c;用于解析并执行传递给它的字符串作为 JavaScript 代码。 二、eval()是用来干什么的&#xff1f; 当调用 eval() 时&#xff0c;它会将传入的字符串参数视为 JavaScript 代码&#xff0c;并在调用位置执…...

JavaScript-console:JavaScript控制台(Console)常用方法

一、理解 console JavaScript 控制台&#xff08;console&#xff09;是一个开发人员在编写 JavaScript 代码时常用的工具。它是浏览器提供的一种界面&#xff0c;让开发人员能够追踪代码执行的状态和结果。JavaScript 控制台可以记录代码输出的信息、警告和错误&#xff0c;并…...

Nginx配置前后端分离

后端地址 1.本地环境 curl --request GET \--url http://localhost:8080/by-admin/captchaImage \--header Authorization: Bearer d7a035d9-b30c-4ca5-8951-8cec90607943确认后端 ip 端口 上下文 2.测试环境 部署到测试环境可能是 换成内网ip和内网服务端口(ip、端口 可能会…...

rabbitmq的发布确认

生产者将信道设置成 confirm 模式&#xff0c;一旦信道进入 confirm 模式&#xff0c; 所有在该信道上面发布的 消息都将会被指派一个唯一的 ID (从 1 开始)&#xff0c;一旦消息被投递到所有匹配的队列之后&#xff0c;broker 就会发送一个确认给生产者(包含消息的唯一 ID)&…...

RISC-V公测平台发布· CoreMark测试报告

一. CoreMark简介 CoreMark是一款用于评估CPU性能的基准测试程序&#xff0c;它包含了多种不同的计算任务&#xff0c;包括浮点数、整数、缓存、内存等方面的测试。CoreMark的测试结果通常被用来作为CPU性能的参考&#xff0c;它可以帮助开发人员和系统管理员评估不同处理器和…...

模型微调(fine-tune)

一、关于模型微调的一些基础知识 1、模型微调&#xff08;fine-tune&#xff09; 微调(fine-tune)通过使用在大数据上得到的预训练好的模型来初始化自己的模型权重&#xff0c;从而提升精度。这就要求预训练模型质量要有保证。微调通常速度更快、精度更高。当然&#xff0c;自己…...

云农场种植:互联网+智慧牧场,为农业注入新的活力和创新

随着科技的不断发展&#xff0c;数字化农业正逐渐成为现代农业的趋势。传统农业面临着土地资源有限、劳动力不足等问题&#xff0c;而云农场种植模式通过数字化技术的运用&#xff0c;互联网养殖着重于“绿色、特色产品和智慧生态”&#xff0c;通过建立“线上养殖线下托养线上…...

Hadoop学习一(初识大数据)

目录 一 什么是大数据&#xff1f; 二 大数据特征 三 分布式计算 四 Hadoop是什么? 五 Hadoop发展及版本 六 为什么要使用Hadoop 七 Hadoop vs. RDBMS 八 Hadoop生态圈 九 Hadoop架构 一 什么是大数据&#xff1f; 大数据是指无法在一定时间内用常规软件工具对其内…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...