力扣面试题 - 40 迷路的机器人 C语言解法
题目:
设想有个机器人坐在一个网格的左上角,网格 r 行 c 列。机器人只能向下或向右移动,但不能走到一些被禁止的网格(有障碍物)。设计一种算法,寻找机器人从左上角移动到右下角的路径。

网格中的障碍物和空位置分别用 1 和 0 来表示。
返回一条可行的路径,路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径,返回空数组。
示例 1:
输入: [[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列(右下角)
说明:r 和 c 的值均不超过 100。
思路:
- 深度优先(DFS)寻找终点。
- 使用visited数组记录走过的路径
- 发现不可行的路径就回溯,直到到达终点
以下C代码有参考题解区大佬:taopi
/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/int visited[100][100];
int DFS(int** obstacleGrid, int r, int c, int x, int y, int** ret, int* len) {// 碰到边界或者障碍,或者重复到达if(x >= r || y >= c || obstacleGrid[x][y] || visited[x][y]){return 0;}ret[*len][0] = x;ret[(*len)++][1] = y;// 到达终点if(x == r - 1 && y == c - 1) {return 1;}visited[x][y] = 1;// 下或者右 有路可走if(DFS(obstacleGrid, r, c, x, y + 1, ret, len) || DFS(obstacleGrid, r, c, x + 1, y, ret, len)){return 1;}// 无路可走,回溯(*len)--;return 0;
}int** pathWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize, int* returnSize, int** returnColumnSizes) {*returnSize = 0;int r = obstacleGridSize, c = *obstacleGridColSize;if(r == 0 || c == 0 || obstacleGrid[0][0] || obstacleGrid[r-1][c-1]) {return NULL;}int** ret = malloc(sizeof(int*) * (r + c));for(int i = 0; i < r + c; i++){ret[i] = malloc(sizeof(int) * 2);}int len = 0;memset(visited, 0, sizeof(visited));if(DFS(obstacleGrid, r, c, 0, 0, ret, &len)) {*returnSize = len;*returnColumnSizes = (int*)malloc(sizeof(int) * len);for(int i = 0; i < len; i++) {(*returnColumnSizes)[i] = 2;}return ret;}for(int i = 0; i < r + c; i++){free(ret[i]);}free(ret);return NULL;
}
相关文章:
力扣面试题 - 40 迷路的机器人 C语言解法
题目: 设想有个机器人坐在一个网格的左上角,网格 r 行 c 列。机器人只能向下或向右移动,但不能走到一些被禁止的网格(有障碍物)。设计一种算法,寻找机器人从左上角移动到右下角的路径。 网格中的障碍物和空…...
ElementPlus 自定义封装 el-date-picker 的快捷功能
文章目录 需求分析 需求 分析 我们看到官网上给出的案例如下,但是不太满足我们用户想要的快捷功能,因为不太多,因此需要我们自己封装一些,方法如下 外部自定义该组件的快捷内容 export const getPickerOptions () > {cons…...
二百八十二、ClickHouse——删除Linux中的ClickHouse
一、目的 由于ClickHosue的库表发生变化,需要删除原有的表结构数据,才能直接把脚本里文件重新安装 二、删除步骤 1、关闭ClickHouse服务 systemctl stop clickhouse-server 2、卸载ClickHouse软件包 sudo yum remove clickhouse-server clickhouse…...
c++ 命名空间使用规则
之前一直没搞懂为什么c 用了using namespace std;就能直接调用内部的类,直接调用内部函数 今天试着实现了一下: #include <iostream>// 命名空间 namespace mp{ class point{public: // 构造函数point(int x 0, int y 0) : x(x), y(y) {}//…...
从 ELK Stack 到简单 — Elastic Cloud Serverless 上的 Elastic 可观察性
作者:来自 Elastic Bahubali Shetti, Chris DiStasio 宣布 Elastic Cloud Serverless 上的 Elastic Observability 正式发布 — 一款完全托管的可观察性解决方案。 随着组织规模的扩大,一个能够处理分布式云环境的复杂性并提供实时洞察的可观察性解决方…...
Pandas系列|第二期:Pandas中的数据结构
1.Pandas中的数据结构:Series和DataFrame Pandas 的主要数据结构是 Series (一维数据)与 DataFrame(二维数据),这两种数据结构足以处理金融、统计、社会科学、工程等领域里的大多数典型用例。 Series 是一…...
Hadoop中MapReduce过程中Shuffle过程实现自定义排序
文章目录 Hadoop中MapReduce过程中Shuffle过程实现自定义排序一、引言二、实现WritableComparable接口1、自定义Key类 三、使用Job.setSortComparatorClass方法2、设置自定义排序器3、自定义排序器类 四、使用示例五、总结 Hadoop中MapReduce过程中Shuffle过程实现自定义排序 一…...
数位dp-acwing
题目:Windy数 1083. Windy数 - AcWing题库 分析 不能有前导0,初始化的时候需要有前导0,因为除了最高位数其他位数可以。 windy : 2 5 1 类似这样的数 第二位与第一位相差3 > 2 分类讨论 : 1. 位数跟 n 同位数 的…...
智慧园区小程序开发制作功能介绍
智慧园区小程序开发制作功能介绍 智慧园区小程序系统作为一款面向园区企业的一站式线上服务平台,可为企业提供数智化的园区办公服务。智慧园区小程序功能介绍 1、园区公告、政策信息查看足不出户掌握最新动态,“园区公告、政策信息”等信息。首页点击对应…...
STM32高级 物联网之Wi-Fi通讯
Wi-Fi基础知识 Wi-Fi由来 Wi-Fi,又称“无线网路”,是Wi-Fi联盟的商标,一个基于IEEE 802.11标准的无线局域网技术。“Wi-Fi”常写作“WiFi”或“Wifi”,但是这些写法并没有被Wi-Fi联盟认可。 Wi-Fi这个术语经常被误以为是指无线保真(Wireless Fidelity),类似历史悠久的…...
LLM预训练recipe — 摘要版
文章核心主题: 本文深入探讨了从零开始进行大型语言模型(LLM)预训练(pretrain)的各个环节,侧重方法论和实践细节,旨在普及预训练过程中的关键步骤、常见问题及避坑技巧,而非技术原理…...
波动理论、传输线和S参数网络
波动理论、传输线和S参数网络 传输线 求解传输线方程 对于传输线模型,我们通常用 R L G C RLGC RLGC 来表示: 其中 R R R 可以表示导体损耗,由于电子流经非理想导体而产生的能量损耗。 G G G 表示介质损耗,由于非理想电介质…...
nginx-1.23.2版本RPM包发布
nginx-1.23.2-0.x86_64.rpm用于CentOS7系统的安装,安装路径与编译安装是同一个路径。安装方法: 将nginx-1.23.2-0.x86_64.rpm上传至目标服务器,执行rpm -ivh nginx-1.23.2-0.x86_64.rpm命令进行安装。 卸载方法: 卸载前先将nginx服…...
如何用WPS AI提高工作效率
对于每位职场人而言,与Word、Excel和PPT打交道几乎成为日常工作中不可或缺的一部分。在办公软件的选择上,国外以Office为代表,而在国内,WPS则是不可忽视的一大选择。当年一代天才程序员求伯君创造了WPS,后面雷军把它装…...
LabVIEW应用在工业车间
LabVIEW作为一种图形化编程语言,以其强大的数据采集和硬件集成功能广泛应用于工业自动化领域。在工业车间中,LabVIEW不仅能够实现快速开发,还能通过灵活的硬件接口和直观的用户界面提升生产效率和设备管理水平。尽管其高成本和初期学习门槛可…...
Elasticsearch:normalizer
一、概述 Elastic normalizer是Elasticsearch中用于处理keyword类型字段的一种工具,主要用于对字段进行规范化处理,确保在索引和查询时保持一致性。 Normalizer与analyzer类似,都是对字段进行处理,但normalizer不会对字段进…...
动态规划子序列问题系列一>等差序列划分II
题目: 解析: 1.状态表示: 2.状态转移方程: 这里注意有个优化 3.初始化: 4.填表顺序: 5.返回值: 返回dp表总和 代码: public int numberOfArithmeticSlices(int[] nums) {in…...
48页PPT|2024智慧仓储解决方案解读
本文概述了智慧物流仓储建设方案的行业洞察、业务蓝图及建设方案。首先,从政策层面分析了2012年至2020年间国家发布的促进仓储业、物流业转型升级的政策,这些政策强调了自动化、标准化、信息化水平的提升,以及智能化立体仓库的建设࿰…...
低代码开源项目Joget的研究——Joget8社区版安装部署
大纲 环境准备安装必要软件配置Java配置JAVA_HOME配置Java软链安装三方库 获取源码配置MySql数据库创建用户创建数据库导入初始数据 配置数据库连接配置sessionFactory(非必须,如果后续保存再配置)编译下载tomcat启动下载aspectjweaver移动jw…...
upload-labs关卡记录15
图片马,这里就可以看到任务和注意事项: 使用一个正常图片,然后拼接一个一句话木马即可实现。这里就用命令窗口进行实现: copy 111.png/b shell.php/a shell.png 注意这里的命令窗口要在存在图片和一句话木马的目录下打开&#…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
