机器人的运动范围

【原题】 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子? 【思路】 主要在于递归的一个过程,并判断符合条件的case,其它的并没有什么好说的,关键是要理解这个过程。另需特别注意:每次为了不重复计算一个单元格,需要开辟一个visited数组来保存哪些元素已经给你访问过,哪些元素还未被访问。

public class Solution {
    public int getSum(int num){
        int count=0;
        while(num!=0){
            count+=num%10;
            num/=10;
        }
        //System.out.println(count);
        return count;
    }
    public int movingCount(int threshold, int rows, int cols)
    {
       boolean[][] visited=new boolean[rows][cols];
        return movingCountCore(threshold,rows,cols,0,0,visited);
    }
    public int movingCountCore(int threshold, int rows, int cols,int row,int col,boolean[][] visited){
        int count=0;   
        System.out.println(row+" "+col);
        if(row>=0&&col>=0&&row<rows&&col<cols&&(getSum(row)+getSum(col))<=threshold&&!visited[row][col])
                {
                visited[row][col]=true;
                    count=1+movingCountCore(threshold,rows,cols,row-1,col,visited)+
                            movingCountCore(threshold,rows,cols,row,col-1,visited)+
                            movingCountCore(threshold,rows,cols,row+1,col,visited)+
                            movingCountCore(threshold,rows,cols,row,col+1,visited);
                }
            return count;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python攻城狮

Python数据科学(九)- 使用Pandas绘制统计图表1.信息可视化

因为人对图像信息的解析效率比文字更高,所以可视化可以使数据更为直观,便于理解,使决策变得高效,所以信息可视化就显得尤为重要。

943
来自专栏北京马哥教育

Numpy 隐含的四大陷阱,千万别掉进去了!

看起来效果不错。假设我们要对数据进行筛选,取第 1 列的第 1 行和第 3 行数据构成一个 2 x 1 的列向量。先看对 array 的做法:

1691
来自专栏有趣的Python

TensorFlow应用实战-19-编写A3C实现赛车游戏

https://www.cnblogs.com/darkknightzh/p/6591923.html

1552
来自专栏北京马哥教育

Numpy 隐含的四大陷阱,千万别掉进去了!

陷阱一:数据结构混乱 array 和 matrix 都可以用来表示多维矩阵: ? 看起来效果不错。假设我们要对数据进行筛选,取第 1 列的第 1 行和第 3 ...

4016
来自专栏落影的专栏

程序员进阶之算法练习(二十四)

前言 已经有三个月未更新算法文章,大厂工作环境是步步紧逼的,使得所有的人越来越忙碌。余下的学习时间,要用于技术预研、知识面开阔、底层原理理解等等,慢慢算法只能占...

4117
来自专栏菩提树下的杨过

NDArray自动求导

NDArray可以很方便的求解导数,比如下面的例子:(代码主要参考自https://zh.gluon.ai/chapter_crashcourse/autogr...

21510
来自专栏互联网大杂烩

机器学习面试

线性回归的因变量是连续变量,自变量可以是连续变量,也可以是分类变量。如果只有一个自变量,且只有两类,那这个回归就等同于t检验。如果只有一个自变量,且有三类或更多...

954
来自专栏互联网杂技

Google用来处理海量文本去重的simhash算法原理及实现

simhash是Google用来处理海量文本去重的算法。 Google出品,你懂的。 simhash最牛逼的一点就是将一个文档,最后转换成一个64位的字节,暂且...

6418
来自专栏ATYUN订阅号

数据清理的简要介绍

清理数据应该是数据科学(DS)或者机器学习(ML)工作流程的第一步。如果数据没有清理干净,你将很难在探索中的看到实际重要的部分。一旦你去训练你的ML模型,他们也...

1123
来自专栏PPV课数据科学社区

如何用spss做一般(含虚拟变量)多元线性回归

回归一直是个很重要的主题。因为在数据分析的领域里边,模型重要的也是主要的作用包括两个方面,一是发现,一是预测。而很多时候我们就要通过回归来进行预测。关...

7747

扫码关注云+社区