题目描述
地上有一个 m 行和 n 列的方格。一个机器人从坐标 0,0 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于 k 的格子。 例如,当 k 为 18 时,机器人能够进入方格(35,37),因为 3+5+3+7 = 18。但是,它不能进入方格(35,38),因为 3+5+3+8 = 19。请问该机器人能够达到多少个格子?
解题思路
回溯法。利用标志位记录已经走过的位置,不过这里不需要对其去标志处理,任何一种方法到达都可以。然后记录在 ret 矩阵中,或者计算标志位中标志的个数。
代码
public class Solution {
public int movingCount(int threshold, int rows, int cols) {
int[] ret = new int[1];
boolean[][] label = new boolean[rows][cols];
canThis(threshold, rows, cols, 0, 0, label, ret);
return ret[0];
}
private void canThis(int threshold, int rows, int cols, int row, int col, boolean[][] label, int[] ret) {
if (row < 0 || col < 0 || row >= rows || col >= cols || label[row][col] == true)
return;
int k = 0;
int tcol = col;
int trow = row;
while (trow != 0) {
k += trow % 10;
trow /= 10;
}
while (tcol != 0) {
k += tcol % 10;
tcol /= 10;
}
if (k <= threshold) {
ret[0]++;
label[row][col] = true;
canThis(threshold, rows, cols, row+1, col, label, ret);
canThis(threshold, rows, cols, row-1, col, label, ret);
canThis(threshold, rows, cols, row, col+1, label, ret);
canThis(threshold, rows, cols, row, col-1, label, ret);
} else
return;
}
}
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于