当前位置: 首页 > 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; 大数据是指无法在一定时间内用常规软件工具对其内…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx

“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网&#xff08;IIoT&#xff09;场景中&#xff0c;结合 DDS&#xff08;Data Distribution Service&#xff09; 和 Rx&#xff08;Reactive Extensions&#xff09; 技术&#xff0c;实现 …...

Linux中INADDR_ANY详解

在Linux网络编程中&#xff0c;INADDR_ANY 是一个特殊的IPv4地址常量&#xff08;定义在 <netinet/in.h> 头文件中&#xff09;&#xff0c;用于表示绑定到所有可用网络接口的地址。它是服务器程序中的常见用法&#xff0c;允许套接字监听所有本地IP地址上的连接请求。 关…...

初级程序员入门指南

初级程序员入门指南 在数字化浪潮中&#xff0c;编程已然成为极具价值的技能。对于渴望踏入程序员行列的新手而言&#xff0c;明晰入门路径与必备知识是开启征程的关键。本文将为初级程序员提供全面的入门指引。 一、明确学习方向 &#xff08;一&#xff09;编程语言抉择 编…...