题目描述
地上有一个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;
}
}