1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| public class Solution { public int movingCount(int threshold, int rows, int columns) { if (threshold < 0 || rows <= 0 || columns <= 0) { return 0; }
boolean[] visited = new boolean[rows * columns]; int count = 0;
count = movingCountCore(threshold, rows, columns, 0, 0, visited);
return count; }
private int movingCountCore(int threshold, int rows, int columns, int row, int column, boolean[] visited) { int count = 0; if (check(threshold, rows, columns, row, column, visited)) { visited[row * columns + column] = true;
count = 1 + movingCountCore(threshold, rows, columns, row - 1, column, visited) + movingCountCore(threshold, rows, columns, row + 1, column, visited) + movingCountCore(threshold, rows, columns, row, column - 1, visited) + movingCountCore(threshold, rows, columns, row, column + 1, visited); }
return count; }
private boolean check(int threshold, int rows, int columns, int row, int column, boolean[] visited) { return row >= 0 && row < rows && column >= 0 && column < columns && getDigitSum(row) + getDigitSum(column) <= threshold && !visited[row * columns + column]; }
private int getDigitSum(int num) { int sum = 0;
while (num > 0) { sum += num % 10; num /= 10; }
return sum; } }
|