剑指offer-机器人的运动范围
题目描述解题思路代码块
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
解题思路
解题思路见代码。
代码块
public class Solution {
public int
movingCount(int threshold
, int rows
, int cols
)
{
boolean
[][] flag
= new boolean[rows
][cols
];
return helper(0, 0, rows
, cols
, threshold
, flag
);
}
public int
helper(int i
, int j
, int rows
,int cols
, int threshold
, boolean
[][] flag
){
if(i
< 0 || j
< 0 || i
>= rows
|| j
>= cols
|| flag
[i
][j
] || (getSum(i
) + getSum(j
) > threshold
)){
return 0;
}
flag
[i
][j
] = true;
return helper(i
- 1, j
, rows
, cols
, threshold
, flag
)
+ helper(i
, j
- 1, rows
, cols
, threshold
, flag
)
+ helper(i
+ 1, j
, rows
, cols
, threshold
, flag
)
+ helper(i
, j
+ 1, rows
, cols
, threshold
, flag
) + 1;
}
int
getSum(int x
){
int sum
= 0;
while( x
!= 0){
sum
+= (x
) % 10;
x
/= 10;
}
return sum
;
}
}
