机器人的运动范围

题目描述

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

思路

与上一题类似，注意这次返回的是int，还要考虑怎么把位数上的数字加起来。先创建一个等大的boolean数组，用来记录走过的路线，然后去扫描当前节点的上下左右，注意要有判断，越界的，已经走过的，不符合要求的都应该返回false，确定递归的结束条件，能进入下一步递归的条件，明确递归方法的作用，开始递归吧！

个人解法

public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        
        //用来判断是否走过这个格子 b数组默认是false
        boolean b[]=new boolean[rows*cols];
        //从00开始递归
        int count=getCount(threshold,rows,cols,0,0,b);
        return count;
        
    }
    public int getCount(int threshould,int rows,int cols,int row,int col,boolean b[]){
        //index得到的是矩阵中的数在一维数组中的位置
        int index=row*cols+col;
        int count=0;
        //如果超出界限，或者大于数字之和或者已经走过了就返回0
        if(row<0||col<0||row>=rows||col>=cols||b[index]||getSum(row)+getSum(col)>threshould){
            return 0;
        }
        //没进入上面的判断，说明这个格子是机器人可以走的 把b[index]标记为true
        b[index]=true;
        
        //开始递归，注意求的是多少个格子，格子一开始从0,0开始，所以加一，然后往这个格子的上下左右递归
       count= 1+getCount(threshould,rows,cols,row-1,col,b)+
            getCount(threshould,rows,cols,row+1,col,b)+
            getCount(threshould,rows,cols,row,col+1,b)+
            getCount(threshould,rows,cols,row,col-1,b);
        return count;
    }
    
    //得到数字各个位数上数字之和
    public int getSum(int a){
        int sum=0;
        while(a>0){
            sum+=a%10;
            a=a/10;
        }
        return sum;
    }
    
}