机器人的运动范围
机器人的运动范围
http://www.nowcoder.com/questionTerminal/6e5207314b5241fb83f2329e89fdecc8
public class Solution {
int threshold;
public int movingCount(int threshold, int rows, int cols) {
// DFS
this.threshold = threshold;
int[][] flag = new int[rows][cols];
return helper(0, 0, rows, cols, flag);
}
private int helper(int i, int j, int row, int col, int[][] flag) {
if(i < 0 || i >= row || j < 0 || j >= col || flag[i][j] == 1
|| numSum(i) + numSum(j) > threshold) {
return 0;
}
flag[i][j] = 1; // 标记已经走过
// 只需要先向下走再一层一层向右走，回溯
return helper(i + 1, j, row, col, flag)
+ helper(i, j + 1, row, col, flag) + 1;
}
private int numSum(int num) {
int sum = 0;
do {
sum += num % 10;
} while((num = num / 10) > 0);
return sum;
}
}