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

力扣面试题 - 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 和 的值均不超过 100。

思路:

  1. 深度优先(DFS)寻找终点。
  2. 使用visited数组记录走过的路径
  3. 发现不可行的路径就回溯,直到到达终点

以下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语言解法

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

ElementPlus 自定义封装 el-date-picker 的快捷功能

文章目录 需求分析 需求 分析 我们看到官网上给出的案例如下&#xff0c;但是不太满足我们用户想要的快捷功能&#xff0c;因为不太多&#xff0c;因此需要我们自己封装一些&#xff0c;方法如下 外部自定义该组件的快捷内容 export const getPickerOptions () > {cons…...

二百八十二、ClickHouse——删除Linux中的ClickHouse

一、目的 由于ClickHosue的库表发生变化&#xff0c;需要删除原有的表结构数据&#xff0c;才能直接把脚本里文件重新安装 二、删除步骤 1、关闭ClickHouse服务 systemctl stop clickhouse-server 2、卸载ClickHouse软件包 sudo yum remove clickhouse-server clickhouse…...

c++ 命名空间使用规则

之前一直没搞懂为什么c 用了using namespace std;就能直接调用内部的类&#xff0c;直接调用内部函数 今天试着实现了一下&#xff1a; #include <iostream>// 命名空间 namespace mp{ class point{public: // 构造函数point(int x 0, int y 0) : x(x), y(y) {}//…...

从 ELK Stack 到简单 — Elastic Cloud Serverless 上的 Elastic 可观察性

作者&#xff1a;来自 Elastic Bahubali Shetti, Chris DiStasio 宣布 Elastic Cloud Serverless 上的 Elastic Observability 正式发布 — 一款完全托管的可观察性解决方案。 随着组织规模的扩大&#xff0c;一个能够处理分布式云环境的复杂性并提供实时洞察的可观察性解决方…...

Pandas系列|第二期:Pandas中的数据结构

1.Pandas中的数据结构&#xff1a;Series和DataFrame Pandas 的主要数据结构是 Series &#xff08;一维数据&#xff09;与 DataFrame&#xff08;二维数据&#xff09;&#xff0c;这两种数据结构足以处理金融、统计、社会科学、工程等领域里的大多数典型用例。 Series 是一…...

Hadoop中MapReduce过程中Shuffle过程实现自定义排序

文章目录 Hadoop中MapReduce过程中Shuffle过程实现自定义排序一、引言二、实现WritableComparable接口1、自定义Key类 三、使用Job.setSortComparatorClass方法2、设置自定义排序器3、自定义排序器类 四、使用示例五、总结 Hadoop中MapReduce过程中Shuffle过程实现自定义排序 一…...

数位dp-acwing

题目&#xff1a;Windy数 1083. Windy数 - AcWing题库 分析 不能有前导0&#xff0c;初始化的时候需要有前导0&#xff0c;因为除了最高位数其他位数可以。 windy &#xff1a; 2 5 1 类似这样的数 第二位与第一位相差3 > 2 分类讨论 &#xff1a; 1. 位数跟 n 同位数 的…...

智慧园区小程序开发制作功能介绍

智慧园区小程序开发制作功能介绍 智慧园区小程序系统作为一款面向园区企业的一站式线上服务平台&#xff0c;可为企业提供数智化的园区办公服务。智慧园区小程序功能介绍 1、园区公告、政策信息查看足不出户掌握最新动态&#xff0c;“园区公告、政策信息”等信息。首页点击对应…...

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 — 摘要版

文章核心主题&#xff1a; 本文深入探讨了从零开始进行大型语言模型&#xff08;LLM&#xff09;预训练&#xff08;pretrain&#xff09;的各个环节&#xff0c;侧重方法论和实践细节&#xff0c;旨在普及预训练过程中的关键步骤、常见问题及避坑技巧&#xff0c;而非技术原理…...

波动理论、传输线和S参数网络

波动理论、传输线和S参数网络 传输线 求解传输线方程 对于传输线模型&#xff0c;我们通常用 R L G C RLGC RLGC 来表示&#xff1a; 其中 R R R 可以表示导体损耗&#xff0c;由于电子流经非理想导体而产生的能量损耗。 G G G 表示介质损耗&#xff0c;由于非理想电介质…...

nginx-1.23.2版本RPM包发布

nginx-1.23.2-0.x86_64.rpm用于CentOS7系统的安装&#xff0c;安装路径与编译安装是同一个路径。安装方法&#xff1a; 将nginx-1.23.2-0.x86_64.rpm上传至目标服务器&#xff0c;执行rpm -ivh nginx-1.23.2-0.x86_64.rpm命令进行安装。 卸载方法&#xff1a; 卸载前先将nginx服…...

如何用WPS AI提高工作效率

对于每位职场人而言&#xff0c;与Word、Excel和PPT打交道几乎成为日常工作中不可或缺的一部分。在办公软件的选择上&#xff0c;国外以Office为代表&#xff0c;而在国内&#xff0c;WPS则是不可忽视的一大选择。当年一代天才程序员求伯君创造了WPS&#xff0c;后面雷军把它装…...

LabVIEW应用在工业车间

LabVIEW作为一种图形化编程语言&#xff0c;以其强大的数据采集和硬件集成功能广泛应用于工业自动化领域。在工业车间中&#xff0c;LabVIEW不仅能够实现快速开发&#xff0c;还能通过灵活的硬件接口和直观的用户界面提升生产效率和设备管理水平。尽管其高成本和初期学习门槛可…...

Elasticsearch:normalizer

一、概述 ‌Elastic normalizer‌是Elasticsearch中用于处理keyword类型字段的一种工具&#xff0c;主要用于对字段进行规范化处理&#xff0c;确保在索引和查询时保持一致性。 Normalizer与analyzer类似&#xff0c;都是对字段进行处理&#xff0c;但normalizer不会对字段进…...

动态规划子序列问题系列一>等差序列划分II

题目&#xff1a; 解析&#xff1a; 1.状态表示&#xff1a; 2.状态转移方程&#xff1a; 这里注意有个优化 3.初始化&#xff1a; 4.填表顺序&#xff1a; 5.返回值&#xff1a; 返回dp表总和 代码&#xff1a; public int numberOfArithmeticSlices(int[] nums) {in…...

48页PPT|2024智慧仓储解决方案解读

本文概述了智慧物流仓储建设方案的行业洞察、业务蓝图及建设方案。首先&#xff0c;从政策层面分析了2012年至2020年间国家发布的促进仓储业、物流业转型升级的政策&#xff0c;这些政策强调了自动化、标准化、信息化水平的提升&#xff0c;以及智能化立体仓库的建设&#xff0…...

低代码开源项目Joget的研究——Joget8社区版安装部署

大纲 环境准备安装必要软件配置Java配置JAVA_HOME配置Java软链安装三方库 获取源码配置MySql数据库创建用户创建数据库导入初始数据 配置数据库连接配置sessionFactory&#xff08;非必须&#xff0c;如果后续保存再配置&#xff09;编译下载tomcat启动下载aspectjweaver移动jw…...

upload-labs关卡记录15

图片马&#xff0c;这里就可以看到任务和注意事项&#xff1a; 使用一个正常图片&#xff0c;然后拼接一个一句话木马即可实现。这里就用命令窗口进行实现&#xff1a; copy 111.png/b shell.php/a shell.png 注意这里的命令窗口要在存在图片和一句话木马的目录下打开&#…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...