地上有一个rows行和cols列的方格。坐标从 [0,0] 到 [rows-1,cols-1]。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于threshold的格子。 例如,当threshold为18时,机器人能够进入方格[35,37],因为3+5+3+7 = 18。但是,它不能进入方格[35,38],因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?
范围:
1 <= rows, cols<= 100
0 <= threshold <= 20
输入:1,2,3
返回值:3
和矩阵中的路径很像,不同的地方主要有两处:
public class Solution {
int iMax, jMax;
int cnt = 0;
boolean[][] arr;
public int movingCount(int threshold, int rows, int cols) {
iMax = rows;
jMax = cols;
arr = new boolean[rows][cols];
dfs(threshold, 0, 0);
return cnt;
}
public void dfs(int threshold, int i, int j) {
if (i >= iMax || i < 0 || j < 0 || j >= jMax || digitSum(i, j) > threshold || arr[i][j]) return;
cnt++;
arr[i][j] = true;
dfs(threshold, i - 1, j);
dfs(threshold, i + 1, j);
dfs(threshold, i, j - 1);
dfs(threshold, i, j + 1);
}
int digitSum(int i, int j) {
int sum = 0;
sum += i % 10;
i /= 10;
sum += i % 10;
sum += j % 10;
j /= 10;
sum += j % 10;
return sum;
}
}
原文:https://www.cnblogs.com/klaus08/p/15228930.html