首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode 489. 扫地机器人(DFS)

LeetCode 489. 扫地机器人(DFS)

作者头像
Michael阿明
发布于 2021-02-19 02:26:33
发布于 2021-02-19 02:26:33
1K00
代码可运行
举报
运行总次数:0
代码可运行

文章目录

1. 题目

房间(用格栅表示)中有一个扫地机器人。 格栅中的每一个格子有空和障碍物两种可能。

扫地机器人提供4个API,可以向前进,向左转或者向右转。每次转弯90度。

当扫地机器人试图进入障碍物格子时,它的碰撞传感器会探测出障碍物,使它停留在原地。

请利用提供的4个API编写让机器人清理整个房间的算法。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
interface Robot {
  // 若下一个方格为空,则返回true,并移动至该方格
  // 若下一个方格为障碍物,则返回false,并停留在原地
  boolean move();

  // 在调用turnLeft/turnRight后机器人会停留在原位置
  // 每次转弯90度
  void turnLeft();
  void turnRight();

  // 清理所在方格
  void clean();
}
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
示例:

输入:
room = [
  [1,1,1,1,1,0,1,1],
  [1,1,1,1,1,0,1,1],
  [1,0,1,1,1,1,1,1],
  [0,0,0,1,0,0,0,0],
  [1,1,1,1,1,1,1,1]
],
row = 1,
col = 3

解析:
房间格栅用01填充。0表示障碍物,1表示可以通过。
机器人从row=1,col=3的初始位置出发。在左上角的一行以下,三列以右。

注意:

输入只用于初始化房间和机器人的位置。你需要“盲解”这个问题。
换而言之,你必须在对房间和机器人位置一无所知的情况下,只使用4个给出的API解决问题。 
扫地机器人的初始位置一定是空地。
扫地机器人的初始方向向上。
所有可抵达的格子都是相连的,亦即所有标记为1的格子机器人都可以抵达。
可以假定格栅的四周都被墙包围。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/robot-room-cleaner 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * class Robot {
 *   public:
 *     // Returns true if the cell in front is open and robot moves into the cell.
 *     // Returns false if the cell in front is blocked and robot stays in the current cell.
 *     bool move();
 *
 *     // Robot will stay in the same cell after calling turnLeft/turnRight.
 *     // Each turn will be 90 degrees.
 *     void turnLeft();
 *     void turnRight();
 *
 *     // Clean the current cell.
 *     void clean();
 * };
 */

class Solution {
    vector<vector<int>> dir = {{-1,0},{0,1},{1,0},{0,-1}};
    unordered_set<string> visited;
public:
    void cleanRoom(Robot& robot) {
        visited.insert("0-0");//坐标访问过
        dfs(robot, 0, 0, 0);
    }
    void dfs(Robot& robot, int x, int y, int d)
    {
        robot.clean();
        int nx, ny, nd;
        string pos;
        for(int k = 1; k <= 4; ++k)
        {   
            robot.turnRight();//换方向      
            nd = (d+k)%4;
            nx = x + dir[nd][0];
            ny = y + dir[nd][1];
            pos = to_string(nx)+"-"+to_string(ny);
            if(visited.count(pos))//下一个位置访问过吗
                continue;
            if(robot.move())//没访问过,可以移动的话
            {
                visited.insert(pos);//访问了
                dfs(robot, nx, ny, nd);//移动
                robot.turnRight();//回溯,调转180度
                robot.turnRight();
                robot.move();//回退到原地
                robot.turnRight();//再转180把方向调到之前走的状态
                robot.turnRight();
            }
        }
    }
};

40 ms 9.9 MB

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/07/25 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
【翻译】.NET 6 中的 dotnet monitor
我们在 2020 年 6 月首次推出了dotnet monitor 作为实验工具,并在去年(2020年)努力将其转变为生产级工具。今天,我很高兴地的宣布 dotnet monitor 的第一个正式版将和 .NET 6 一起发布,作为 .NET 6 的一部分。
晓晨
2021/12/09
6730
【翻译】.NET 6 中的 dotnet monitor
使用dotnet-monitor sidecar模式 dump docker运行的dotnet程序.
随着容器和云技术的发展, 大量的应用运行在云上的容器中, 它们的好处是毋庸置疑的, 例如极大的提高了我们的研发部署速度, 快速的扩缩容等等, 但是也存在一些小小的问题, 例如难以调试. 基于VM的部署我们可以通过安全的方式登录到主机上做一些你想做的事情, 但是云上的容器那就是不太方便了(目前AWS的ECS已经有类似docker exec的方式直接进入容器中了, 其他的云未作了解). 但是就算能进入容器也不意味着调试就好做了, 通常来说使用的镜像都是经过优化和精简的(如果要调式可能需要安装大量的组件).
旺财的城堡
2022/11/02
1.5K0
使用dotnet-monitor sidecar模式 dump docker运行的dotnet程序.
当 dotnet-monitor 遇上 Prometheus, 是种什么样的体验?
对于开发和运维人员来说, 监控大屏很棒, 让我们来做一个 Dashboard 吧!大家可能听说过一些 CLI 诊断工具, 比如 dotnet-counters,dotnet-dump 和 dotnet-trace, 那 dotnet-monitor 又是什么呢?简单理解就是把上面的几种诊断工具进行了包装, 并且暴露了 对应的 REST API, 让诊断变的更容易, 在去年, dotnet-monitor 还是一个实验性的诊断工具, 当时我也写了一篇文章介绍 dotnet-monitor,使用 dotnet-monitor 分析.NET 应用程序 , 而最近, .NET 团队宣布第一个 release 版本的 dotnet-monitor, 同时它也是 .NET 6 的内容, 也就是 dotnet-monitor 6.0.0 !
全球技术精选
2021/12/07
6850
当 dotnet-monitor 遇上 Prometheus, 是种什么样的体验?
如何创建一个带诊断工具的.NET镜像
现在是云原生和容器化时代,.NET Core对于云原生来说有非常好的兼容和亲和性,dotnet社区以及微软为.NET Core提供了非常方便的镜像容器化方案。所以现在大多数的dotnet程序都是部署在各种容器化环境中,比如我们常见的Docker。
InCerry
2022/11/14
2.4K0
Docker最全教程——.NET5进一步拥抱容器技术
.NET 5已经发布多时了,众所周知,其对容器的支持又上了一个台阶。那么主要有哪些变化呢,接下来我们一起来了解吧。
雪雁-心莱科技
2020/12/14
1.3K0
动手实现一个适用于.NET Core 的诊断工具
大家可能对诊断工具并不陌生,从大名鼎鼎的 dotTrace,到 .NET CLI 推出的一系列的高效诊断组件(dotnet trace,dotnet sos,dotnet dump)等, 这些工具提升了对程序Debug的能力和效率,可以让开发人员从更高层次的维度来发现程序中的问题。
全球技术精选
2021/05/18
6660
动手实现一个适用于.NET Core 的诊断工具
.NET 中的 EventCounters
EventCounters 是 .NET API,用于轻量级、跨平台、准实时性能指标收集。 EventCounters 作为 Windows 上 .NET 框架的“性能计数器”的跨平台替代项添加。 本文将介绍什么是 EventCounters,如何实现它们,以及如何使用它们。
呆呆
2022/01/07
1.7K0
dotnet-trace 性能分析实用工具
若要安装最新版 dotnet-trace NuGet 包,请使用 dotnet tool install 命令:
呆呆
2022/01/09
1.4K0
使用 PerfCollect 跟踪 .NET 应用程序
在 Linux 上遇到性能问题时,可使用 perfcollect 收集跟踪,以便收集有关出现性能问题时计算机上发生的状况的详细信息。
呆呆
2022/01/09
1.5K0
记一次ASP.NET CORE线上内存溢出问题与dotnet-dump的排查方法
项目又都运行在docker容器中,容器为了最小化,采用了极简的系统,几乎任何常见命令都没有.
GuZhenYin
2025/05/17
3800
记一次ASP.NET CORE线上内存溢出问题与dotnet-dump的排查方法
构建 dotnet&vue 应用镜像->推送到 Nexus 仓库->部署为 k8s 服务实践
不管什么语言,基本都可以使用这个打包流程,将官方镜像打包推送到私有镜像仓库个人认为是必要的,不然如果一旦远端的镜像失效,又需要重新拉取镜像时就会很尬尴。
易墨
2024/01/03
7770
构建 dotnet&vue 应用镜像->推送到 Nexus 仓库->部署为 k8s 服务实践
.NET Core CLI 的性能诊断工具介绍
开发人员的.NET Core项目上线后,经常会出现各种问题,内存泄漏,CPU 100%,处理时间长等, 这个时候就需要快速并准确的发现问题,并解决问题, 除了项目本身的日志记录外,NET Core 为我们开发人员提供了一系列功能强大并且无侵入的诊断工具,本文主要介绍的是 .NET Core dotnet 诊断全局工具
梁规晓
2020/11/05
1.2K0
.NET Core CLI 的性能诊断工具介绍
调试 .NET Core 中的高 CPU 使用率
本教程将介绍如何调试 CPU 使用率过高的情况。 使用提供的示例 ASP.NET Core Web 应用 源代码存储库,可以故意造成死锁。 终结点将停止响应并遇到线程累积问题。 你将了解如何使用各种工具,通过几条关键的诊断数据诊断此情况。
呆呆
2022/01/09
1.6K0
《.NET 5.0 背锅案》第1集:验证 .NET 5.0 正式版 docker 镜像问题
今天我们分析了博客站点的2次故障(故障一、故障二),发现一个巧合的地方,.NET 5.0 正式版的 docker 镜像是在11月10日提前发布上线的。
huofo
2022/03/17
5050
《.NET 5.0 背锅案》第1集:验证 .NET 5.0 正式版 docker 镜像问题
每周.NET前沿技术文章摘要(2017-05-17)
本文介绍了.NET技术相关的文章,包括.NET Core, .NET Standard, ASP.NET, 性能分析等方面的内容。
张善友
2017/05/17
1.3K0
使用Docker buildx 为 .NET 构建多平台镜像
.NET 团队有一篇博客 改进多平台容器支持, 详细介绍了.NET 7 以上的平台可以轻松的使用Docker buildx 工具构建多平台的镜像。 buildx 是 Docker 官方提供的一个构建工具,它可以帮助用户快速、高效地构建 Docker 镜像,并支持多种平台的构建。使用 buildx,用户可以在单个命令中构建多种架构的镜像,例如 x86 和 ARM 架构,而无需手动操作多个构建命令。此外,buildx 还支持 Dockerfile 的多阶段构建和缓存,这可以大大提高镜像构建的效率和速度。
张善友
2023/10/18
7260
使用Docker buildx 为 .NET 构建多平台镜像
aspire-dashboard 的各种认证方式
之前我们有介绍过如何使用 Aspire Dashboard 使用 aspire-dashboard 展示 open-telemetry trace/logging/metrics, 最近在将几个系统集成 Aspire 想要将 aspire dashboard 部署为自己系统的一部分,同时接入自己的用户系统来实现认证授权,发现 Aspire Dashboard 已经支持了 OpenIdConnect 的认证方式,集成起来还是比较简单的,下面介绍下 aspire dashboard 的各种认证方式
郑子铭
2025/04/09
1640
aspire-dashboard 的各种认证方式
译 | .NET Core 3.0 Preview 6 已发布
今天,我们宣布 .NET Core 3.0 Preview 6。它的更新包括编译程序集以改进启动、使用链接器和 EventPipe 改进优化应用程序的大小。我们还在 ARM64 上发布了针对 Alpine 的新 Docker 镜像。
Edi Wang
2019/07/09
1.2K0
译 | .NET Core 3.0 对诊断的改进
在 .NET Core 3.0 中,我们将引入一套工具,这些工具利用 .NET 运行时中的新功能,使诊断和解决性能问题变得更加容易。
Edi Wang
2019/07/09
2K0
传统.NET 4.x应用容器化体验(2)
上一篇我们基于Windwos Server 2019 with Container初步跑了一个ASP.NET WebForm应用程序。本篇我们来自己编译部署一个ASP.NET MVC应用程序到Windows Container。
Edison Zhou
2021/07/21
1.7K0
传统.NET 4.x应用容器化体验(2)
相关推荐
【翻译】.NET 6 中的 dotnet monitor
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档