机器人的运动范围 -- java
题目描述
地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动,它每次可以向左、右、上、下四个方向移动一格,但是不能进入行坐标和列坐标的 数位之和 大于 k 的格子。
例如,当 k 为 18 时,机器人能够进入方格(35, 37),因为 3+5+3+7=18。但是,它不能进入方格(35, 38),因为 3+5+3+8=19。请问该机器人能够达到多少个格子?
题目考点
- 考察应聘者对回溯法的理解。通常物体或者人在二维方格运行这类问题都可以使用回溯法解决。
- 考察应聘者对数组的编程能力。我们一般都把矩阵看成一个二维数组。只有对数组的特性充分了解,只有可能快速、正确得实现回溯法的代码。
代码
public class MovingCount {
// 给用户直接调用的方法,统计运动范围格子数
public static int movingCount(int threshold, int rows, int cols) {
// 不合法输入判断
if (threshold < 0 || rows <= 0 || cols <= 0) {
return 0;
}
// 设置一个已访问的列表
boolean[] visited = new boolean[rows * cols];
// 从坐标 (0,0) 开始进入
int count = movingCountCore(threshold, rows, cols, 0, 0, visited);
return count;
}
// 核心方法,真正的统计运动范围格子数
public static int movingCountCore(int threshold, int rows, int cols, int row, int col, boolean[] visited) {
int count = 0;
if (check(threshold, rows, cols, row, col, visited)) {
visited[row * cols + 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;
}
// 判断机器人能否进入坐标为(row,col)的方格
public static boolean check(int threshold, int rows, int cols, int row, int col, boolean[] visited) {
if (row >= 0 && row < rows && col >= 0 && col < cols
&& getDigitSum(row) + getDigitSum(col) <= threshold
&& !visited[row * cols + col]) {
return true;
} else {
return false;
}
}
// 用来得到一个数字的数位之和
public static int getDigitSum(int number) {
int sum = 0;
while (number > 0) {
sum += number % 10;
number /= 10;
}
return sum;
}
// 测试
public static void main(String[] args) {
System.out.println(movingCount(18, 99, 99));
}
}
来自:
《剑指Offer》
Coding-Interviews/机器人的运动范围.md at master · todorex/Coding-Interviews