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

2018-07-12 admin

题目描述

地上有一个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); 决定该位置是否合法要检查这么几个方面:

  1. x、y坐标不能超出rows和cols的界限
  2. 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;
}

原文链接:https://segmentfault.com/a/1190000015605759

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-35793.html

文章标题:【刷算法】求机器人的运动范围

相关文章
12个你未必知道的CSS小知识
虽然CSS并不是一种很复杂的技术,但就算你是一个使用CSS多年的高手,仍然会有很多CSS用法/属性/属性值你从来没使用过,甚至从来没听说过。 1.CSS的color属性并非只能用于文本显示 对于CSS的color属性,相信所有Web开发人员...
2015-11-12
ajax为什么令人惊异?ajax的优缺点
使用Ajax的最大优点,就是能在不更新整个页面的前提下维护数据。这使得Web应用程序更为迅捷地回应用户动作,并避免了在网络上发送那些没有改变的信息。 Ajax不需要任何浏览器插件,但需要用户允许JavaScript在浏览器上执行。就像DHT...
2015-11-12
HTML5的5个不错的开发工具推荐
HTML5规范终于在今年正式定稿,对于从事多年HTML5开发的人员来说绝对是一个重大新闻。数字天堂董事长,DCloud CEO王安也发表了文章,从开发者和用户两个角度分析了HTML对两个人群的优势。其实,关于HTML5的开发工具,我们以往的...
2015-11-12
JavaScript教程:JS中的原型
Keith Peters 几年前发表的一篇博文,关于学习没有“new”的世界,其中解释了使用原型继承代替构造函数。两者都是纯粹的原型编码。 标准方法(The Standard Way) 一直以来,我们学习的在 JavaScript 里创建对...
2015-11-12
css布局的各种FC简单介绍:BFC,IFC,GFC,FFC
什么是FC? Formatting Context,格式化上下文,指页面中一个渲染区域,拥有一套渲染规则,它决定了其子元素如何定位,以及与其他元素的相互关系和作用。 BFC 什么是BFC Block Formatting Context,块...
2018-05-17
AJAX的浏览器支持
AJAX 的要点是 XMLHttpRequest 对象。 不同的浏览器创建 XMLHttpRequest 对象的方法是有差异的。 IE 浏览器使用 ActiveXObject,而其他的浏览器使用名为 XMLHttpRequest 的 Jav...
2015-11-12
JavaScript的组成
一个完整的JavaScript由3个部分组成:核心(ECMAScript) 文档对象模型(DOM) 浏览器对象模型(BOM) ECMAScript 描述了该语言的语法和基本对象 ; DOM 描述了处理网页内容的方法和接口 ; BOM 描...
2015-11-12
Riot.js:不足1KB的MVP客户端框架
Riot.js是一款MVP(模型-视图-呈现)开源客户端框架,其最大的特点就是体积非常小,不足1KB,虽然体积小,但它可以帮助用户构建大规模的Web应用程序。 Riot.js是由Moot公司开发,目前最新版本为v0.9.2,遵循MIT开源许...
2016-03-11
typeof、instanceof和contructor的区别
typeof:以字符串的形式返回变量的原始类型,typeof在两种情况下会返回&quot;undefined&quot;:一个变量没有被声明的时候,和一个变量的值是undefined的时候,注意,typeof null也会返回object,...
2015-11-12
必须记住的 30 类 CSS 选择器
开篇 有 30 个 CSS 选择器你必须烂熟于心,它们适应于当今各大主流浏览器。 1.* * { margin: 0; padding: 0; } *选择器选择的是每一个单一元素。很多程序员用上面的 CSS 将所有元素的 ma...
2015-11-16
回到顶部