【刷算法】求机器人的运动范围

AlphaWatch 发布于2019-08-22 18:40 / 3108人阅读

摘要：一个机器人从坐标的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于的格子。例如，当为时，机器人能够进入方格，因为。

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

分析

对于每个到(x,y)的机器人，有四种移动可能，上下左右，即：(x+1,y)，(x-1,y)，(x,y-1)，(x,y+1)；

决定该位置是否合法要检查这么几个方面：

x、y坐标不能超出rows和cols的界限

x、y的坐标数位之和不能大于k

代码实现

function movingCount(k, rows, cols)
{
    var flags = [];
    for(var i = 0;i < rows;i++) {
        flags.push([]);
        for(var j = 0;j < cols;j++) {
            flags[i].push(0);
        }
    }
    
    return steps(0,0,rows,cols,flags, k);
}
function steps(x, y, rows, cols, flags, k){
    if(x <0 || x >= rows || y < 0 || y >= cols || flags[x][y] === 1 || (bitSum(x) + bitSum(y) > k) )
        return 0;
    flags[x][y] = 1;
    return steps(x-1, y, rows, cols, flags, k) + steps(x+1, y, rows, cols, flags, k) + steps(x, y-1, rows, cols, flags, k) + steps(x, y+1, rows, cols, flags, k) + 1;
}

function bitSum(n){
    var sum = 0;
    while(n >= 1){
        sum += n%10;
        n = Math.floor(n/10);

    }
    return sum;
}

GPU云服务器云服务器机器学习的算法常用的机器学习算法 java算法求素数 webrtc复数求模快速算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96065.html

为什么需要微积分

摘要：以解析几何作为基础，为微积分的研究创立开辟了道路，它用于研究数图形运动以及变化。莱布尼茨创造的微积分符号更优秀，并沿用至今。推动人类进程，微积分是人类研究自然规律的基本工具，使人们对事物的认知有了飞跃。微积分我们知道数学是人类描述自然规律的语言将现实世界进行抽象，有了数学这个工具就能让我们对物体数量、物体结构、物体的空间、物体的运动等进行抽象量化描述。现今的数学已经发展出很多分支，微积分也...

wushuiyong 2019-05-21 19:27 评论0 收藏0
SegmentFault 技术周刊 Vol.30 - 学习 Python 来做一些神奇好玩的事情吧

摘要：学习笔记七数学形态学关注的是图像中的形状，它提供了一些方法用于检测形状和改变形状。学习笔记十一尺度不变特征变换，简称是图像局部特征提取的现代方法基于区域图像块的分析。本文的目的是简明扼要地说明的编码机制，并给出一些建议。 showImg(https://segmentfault.com/img/bVRJbz?w=900&h=385); 前言开始之前，我们先来看这样一个提问： pyth...

lifesimple 2019-07-30 14:22 评论0 收藏0