机器人的运动范围

【原题】 地上有一个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 条评论
登录 后参与评论

相关文章

来自专栏生信技能树

ChAMP 包分析450K甲基化芯片数据(一站式)

就有非常棒的一站式教程投稿,也因此我结识了优秀的六六,以及其教程大力推荐的R包作者,见:

1652
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet系列 之 随机选择

  平日工作学习时总会遇到一些令人欣喜的代码段子(Snippet),虽然都很短小,但是其间所含的道理都颇有意味,遂而觉得应该不时的将她们记下,一来算作复习整理,...

922
来自专栏鸿的学习笔记

写给开发者的机器学习指南(十二)

此代码加载DJI数据,并将其添加到已经包含我们自己的股票市场指数的图形上。但是,当我们执行这段代码时,结果如下。

902
来自专栏潇涧技术专栏

Python Algorithms - C2 The basics

本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。

852
来自专栏琯琯博客

一个有用的PHP片段的集合

2597
来自专栏程序人生

谈谈FRP和Observable(一)

Observable是方兴未艾的FRP(Functional Reactive Programming)革命里最引人注目的一把火炬。FRP发展了也有两年多了,至...

4577
来自专栏nimomeng的自我进阶

探索命名之美(一)

很多新码农在工作中总会被老鸟批评程序命名的陋习,我也被批评过很多次。痛定思过,我决定要研究应该怎么命名,为什么要给函数一个好的命名很难,应该怎么样给函数命名。

1073
来自专栏转载gongluck的CSDN博客

FFmpeg菜鸡互啄#第5篇#视频帧格式转换

关键步骤 int rgbsize = avpicture_get_size(PIX_FMT_RGB24, pVCodecCtx->width, pVCo...

4096
来自专栏技术总结

UIKit Dynamics 置身真实世界

24010
来自专栏顶级程序员

为什么Python是入行人工智能的首选语言?

在所有编程语言里,Python并不算萌新,从1991年发布第一个版本,至今已经快30年了。

1164

扫码关注云+社区