机器人

大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。


今天分享的题目来源于剑指 Offer 系列 面试题 13. 机器人的运动范围

题目汇总链接:https://www.algomooc.com/jianzhioffer

一、题目描述

地上有一个 m 行 n 列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标[0, 0]的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于 k 的格子。例如,当 k 为 18 时,机器人能够进入方格[35, 37],因为 3 + 5 + 3 + 7 = 18 。但它不能进入方格 [35, 38],因为 3 + 5 + 3 + 8 = 19。

请问该机器人能够到达多少个格子?

示例 1:

输入:m = 2, n = 3, k = 1
输出:3

示例 2:

输入:m = 3, n = 1, k = 0
输出:1

提示:

  • 1 <= n,m <= 100
  • 0 <= k <= 20

二、题目解析

我们依旧用 四步分析法 进行结构化的分析,帮助我们思考和发现规律,写出合理的代码。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1、模拟

我们需要统计能走多少个格子,不能少统计也不能重复统计。

  • 避免少统计:遍历所有能移动的格子
  • 避免重复统计:每次统计完一个格子,将其移除

由于机器人是从左上角(0,0) 开始移动,所以移动方向必然是 下方 或者 右方,即机器人从格子的 左方 或者 上方 进入格子,从格子的 下方 或者 右方 离开格子。

接下来依次观察一下随着 k 的变大,符合要求的区域是哪些。

注:符合要求的区域并不代表机器人一定能够到达,因为中间有一些不符合要求的区域,机器人无法跨越。

当 k = 0 时:

剑指 Offer 13. 机器人的运动范围.006

当 k = 1 时:

剑指 Offer 13. 机器人的运动范围.007

当 k = 2 时:

剑指 Offer 13. 机器人的运动范围.008

当 k = 3 时:

剑指 Offer 13. 机器人的运动范围.009

当 k = 4 时:

剑指 Offer 13. 机器人的运动范围.010

我们以 k = 4 为例,演示机器人的移动。

剑指 Offer 13. 机器人的运动范围.012

剑指 Offer 13. 机器人的运动范围.013

剑指 Offer 13. 机器人的运动范围.014

剑指 Offer 13. 机器人的运动范围.015

剑指 Offer 13. 机器人的运动范围.016

当机器人移动到 4 这个格子的时候,无法再向下移动,因为下方的 5 超过了 4,属于无法进入的区域,根据我们之前的结论,机器人需要向右移动,此时右方的 5 也超过了 4,机器人无法再移动到任何一个新的格子,需要返回,左方是边界,因此只能向上返回,在返回的同时需要携带统计到的格子,避免遗失

为了方便演示,在每个格子的四周分别设置一个小方块,表示机器人由此格子出发可到达区域的数量,实际上,我们只需要观察格子的下方和右方统计数即可,因为机器人只能此格子的 下方 或者 右方 离开格子,返回时也必然从此格子的 下方 或者 右方 返回到此格子并带来了统计的数量。

剑指 Offer 13. 机器人的运动范围.021

剑指 Offer 13. 机器人的运动范围.022

机器人从 4 返回 3 的同时,携带着统计的数量 1,记录在格子 3 的下方,表明机器人由 3 这个格子出发可到达区域的数量为 1,同时,为了避免多次统计格子 4,将格子 4 的状态清除。

剑指 Offer 13. 机器人的运动范围.023

接下来,让机器人从格子 3 的右方开始出发,探索右方可到达的区域。

剑指 Offer 13. 机器人的运动范围.025

到达格子 4 后,下方和右方都不可到达,返回并携带数量,同时清除状态。

剑指 Offer 13. 机器人的运动范围.028

接下来,机器人不断的重复从一个格子出发探索、返回携带数量、清除区域的操作。

剑指 Offer 13. 机器人的运动范围.029

剑指 Offer 13. 机器人的运动范围.034

剑指 Offer 13. 机器人的运动范围.037

剑指 Offer 13. 机器人的运动范围.039

剑指 Offer 13. 机器人的运动范围.043

剑指 Offer 13. 机器人的运动范围.047

剑指 Offer 13. 机器人的运动范围.048

剑指 Offer 13. 机器人的运动范围.049

剑指 Offer 13. 机器人的运动范围.050

最终统计出,当 k = 4 的时候,机器人可移动到达的格子数量为 15

2、规律

在搜索过程中,如果下方格子与右方格子不符合要求,则向上或者向左返回上一个格子

3、匹配

机器人先从一个方向出发,直到到达不可到达的区域时才返回,符合 深度优先遍历 的性质。

机器人不断的重复从一个格子出发探索、返回携带数量、清除区域的操作,符合 递归 的性质。

所以,我们可以使用一个数组用来记录符合要求的格子是否被机器人访问过,若没有访问过,则在机器人返回的过程中将结果 + 1。

具体操作如下:(参考自 Krahets

  • 递归参数:当前元素在矩阵中的行列索引 i 和 j
  • 终止条件: ① 行列索引越界 ② 数位和超出目标值 k ,即不满足行坐标和列坐标的数位之和小于 k 的格子

③ 已经被访问过的重复格子

  • 递推工作: 标记当前单元格 :将索引 (i, j) 存入临时变量 visited 中,代表此单元格已被访问过。

搜索下一单元格: 计算当前元素的 下、右 两个方向元素的数位和,并开启下层递归 。

  • 回溯返回值: 返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数,代表从本单元格递归搜索的可达解总数。

4、边界

  • 超出边界的格子
  • 已经被访问过的重复格子
  • 不满足行坐标和列坐标的数位之和小于 k 的格子

三、动画描述

四、图片描述

剑指 Offer 13. 机器人的运动范围.004

剑指 Offer 13. 机器人的运动范围.005

剑指 Offer 13. 机器人的运动范围.006

剑指 Offer 13. 机器人的运动范围.007

剑指 Offer 13. 机器人的运动范围.008

剑指 Offer 13. 机器人的运动范围.009

剑指 Offer 13. 机器人的运动范围.010

剑指 Offer 13. 机器人的运动范围.011

剑指 Offer 13. 机器人的运动范围.012

剑指 Offer 13. 机器人的运动范围.013

剑指 Offer 13. 机器人的运动范围.014

剑指 Offer 13. 机器人的运动范围.015

剑指 Offer 13. 机器人的运动范围.016

剑指 Offer 13. 机器人的运动范围.017

剑指 Offer 13. 机器人的运动范围.018

剑指 Offer 13. 机器人的运动范围.019

剑指 Offer 13. 机器人的运动范围.020

剑指 Offer 13. 机器人的运动范围.021

剑指 Offer 13. 机器人的运动范围.022

剑指 Offer 13. 机器人的运动范围.023

剑指 Offer 13. 机器人的运动范围.024

剑指 Offer 13. 机器人的运动范围.025

剑指 Offer 13. 机器人的运动范围.026

剑指 Offer 13. 机器人的运动范围.027

剑指 Offer 13. 机器人的运动范围.028

剑指 Offer 13. 机器人的运动范围.029

剑指 Offer 13. 机器人的运动范围.030

剑指 Offer 13. 机器人的运动范围.031

剑指 Offer 13. 机器人的运动范围.032

剑指 Offer 13. 机器人的运动范围.033

剑指 Offer 13. 机器人的运动范围.034

剑指 Offer 13. 机器人的运动范围.035

剑指 Offer 13. 机器人的运动范围.036

剑指 Offer 13. 机器人的运动范围.037

剑指 Offer 13. 机器人的运动范围.038

剑指 Offer 13. 机器人的运动范围.039

剑指 Offer 13. 机器人的运动范围.040

剑指 Offer 13. 机器人的运动范围.041

剑指 Offer 13. 机器人的运动范围.042

剑指 Offer 13. 机器人的运动范围.043

剑指 Offer 13. 机器人的运动范围.044

剑指 Offer 13. 机器人的运动范围.045

剑指 Offer 13. 机器人的运动范围.046

剑指 Offer 13. 机器人的运动范围.047

剑指 Offer 13. 机器人的运动范围.048

剑指 Offer 13. 机器人的运动范围.049

剑指 Offer 13. 机器人的运动范围.050

剑指 Offer 13. 机器人的运动范围.051

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public int movingCount(int m, int n, int k) {
     // 使用临时变量 visited 记录格子是否被访问过
     boolean[][] visited = new boolean[m][n];
     // 开始深度优先遍历
     return dfs(0, 0, m, n, k, visited);
    }

    public int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
         // 行列索引越界 
        if( i >= m || j >= n ) return 0;
    
        // 数位和超出目标值 k ,即不满足行坐标和列坐标的数位之和小于 k 的格子
        if( k < sum( i , j ) ) return 0;
     
         // 已经被访问过的重复格子
        if ( visited[i][j] ) return 0;
    
         //机器人进入了一个新格子,标注这个格子被访问过
         visited[i][j] = true;
    
        //沿着当前格子的右边和下边继续访问
        return 1 + dfs( i + 1, j , m ,  n , k , visited ) + dfs( i , j + 1, m , n , k , visited);
    
    }

    //计算两个坐标数字的和
    private int sum(int i, int j) {
        int sum = 0;
   
        while (i != 0) {
             // 通过求余和取整的操作来计算
             sum += i % 10;
             i /= 10;
         }
        while (j != 0) {
            sum += j % 10;
             j /= 10;
          }
        return sum;
    }
}

六、复杂度分析

时间复杂度

时间复杂度:O(m * n)

空间复杂度

空间复杂度:O(m * n)

七、相关标签

  • 深度优先搜索
  • 递归
  • 数组
  • 回溯

八、参考链接

  • https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/
  • https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
  • https://www.algomooc.com/263.html

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员吴师兄

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 让你比机器人更机器人

    鉴于苹果推出智能手表Apple Watch后引发疯狂的喧嚣,你可能认为可穿戴设备将成为科技发展方向的下一个重要转折点。尽管可穿戴设备的热度现在如日中天,但其实它...

    机器人网
  • 机器人

    今天给大家讲一讲微信的新功能,微信对话开放平台的小程序对接及使用拓展方法!相当于有了一个手机版某爱同学了,功能真的不可谓不强大!还自带游戏功能,之后甚至可以根据...

    用户6267359
  • CB Insights机器人报告:机器人崛起

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

    点滴科技资讯
  • python 微信机器人-如何调用机器人的api,调用图灵机器人接口演示。调用机器人原理,图灵机器人注册。

    我们调用的是图灵机器人,这个apiUrl就是图灵机器人提供给我们的api接口。 接下来给大家演示一下怎么来调用自己的机器人。

    小蓝枣
  • 混合型机器人---直角坐标机器人与关节机器人的有机结合

    直角坐标机器人被广泛应用于各种自动化生产线中完成码垛搬运、上下料、供料、装配、检测、焊接和涂胶等任务。它以行程大,负载能力强,精度高,组合方便,性价比非常高,易...

    机器人网
  • 【孙富春】新一代机器人:云脑机器人

    清华大学计算机科学与技术系;智能技术与系统国家重点实验室;清华信息科学与技术国家实验室 ? 【孙富春】清华大学计算机科学与技术系教授,博士生导师,全国优秀博士论...

    新智元
  • 钉钉机器人

    王兵
  • 微信机器人

    使用它可以方便的完成 回复消息、搜索好友、被添加自动回复、获取好友信息等功能,当然功能不止于这些,这里我们用到了回复信息功能

    双鬼带单
  • 机器人世界

    与人类一样,机器人通过它的“感官”来感知世界。例如,无人驾驶汽车使用视频、雷达与激光雷达来观察周围的世界。随着汽车不断地收集数据,它们会建立起一个3D观察世界,...

    小飞侠xp
  • python QQ机器人

    github地址:https://github.com/babyshen/Python/blob/master/qq%E6%9C%BA%E5%99%A8%E4%...

    py3study
  • 管道机器人

    “管道”被广泛使用在煤气输送、水流疏导、石油化工以及热电蒸气传输领域,是日常生活中不可缺少的一环。管道与陆路、水路、空路运输工具一道,构成了油料、燃气的主要传送...

    ZC_Robot机器人技术
  • 认识机器人

    这几年随着人工智能和机器人的各种概念兴起,机器人被越来越多人所了解和熟知。随便问一个人都知道机器人,并且也都能说出一二;尽管都知道机器人,还是有一部分人觉得机器...

    叶子陪你玩
  • 机器人产业链分析-机器人基本知识

    机器人是一个广义的词语,机器人(Robot)是自动执行工作的机器装置。它既可以接受人类指挥,又可以运行预先编排的程序,也可以根据以人工智能技术制定的原则纲领行动...

    企鹅号小编
  • 【机器人小知识】机器人主要参数介绍

    重复定位精度、可动范围、手部负载,这些术语究竟代表些什么?本篇将要介绍的是机器人的主要参数,看完后相信你会对机器人参数不再陌生。 手部负载条件 使用机器人时应保...

    机器人网
  • 机器人软件开发:机器人开源库安装

    现在的机器人研发已经从闭源过渡到开源时代,开源库的兴起加速了机器人的研发进程。目前大都数的机器人开源库主要用于机器人建模、仿真和控制。以下列举几种常见的建模仿真...

    ZC_Robot机器人技术
  • python itchat+机器人web api实现个人微信机器人

    程序员同行者
  • 工业机器人编程教程-机器人编程运动

    1、机器人的运动类型 ? 2、PTP运动 (1)PTP运动简要介绍 PTP运动示意图 ? 同步运动PTP 在一个PTP运动中,参与运动的轴中运动距离组长的被称之...

    企鹅号小编
  • 现实中的机器人“大白”和微磁力机器人

    ---- 不管喷火、磁悬浮车盘、等离子切割还是能粘住一切的化学材料,在由数以万计的微型磁力机器人组成的“变形金刚”前都相继失色,在最近上映的热门动画片《超能陆...

    机器人网
  • ROS2之机器人辅助医疗 (医护服务机器人)

    演讲分享了新加坡公共医疗保健领域采用机器人技术和智能系统的路线图以及复杂且分散的技术系统与HIT和基础架构之间的互操作性需求。 由卫生部任命的医疗辅助与机器人技...

    zhangrelay

扫码关注云+社区

领取腾讯云代金券