题解 | #机器人的运动范围#回溯法

public class Solution {
    public int movingCount(int threshold, int rows, int cols) {

        if (threshold < 0 || rows <= 0 || cols <= 0){
            return 0;
        }

        boolean[][] visited = new boolean[rows][cols];

        return countByDFS(threshold,0,0,visited,rows,cols);

    }

    private int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    private int countByDFS(int threshold,int row,int col,boolean[][] visited,int rows,int cols){
        int count = 0;
        if (validCheck(threshold,row,col,visited,rows,cols)){

            visited[row][col] = true;
            count++;
            for (int[] dir : dirs) {
                count += countByDFS(threshold,row+dir[0],col+dir[1],visited,rows,cols);
            }
        }

        return count;
    }


    private boolean validCheck(int threshold,int row,int col,boolean[][] visited,int rows,int cols){

        if (row < 0 || col < 0 || row >= rows || col >= cols || visited[row][col] || (getSum(row) + getSum(col)) > threshold){

            return false;
        }

        return true;
    }

    private int getSum(int num){

        int sum = 0;

        while ( num > 0 ){

            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}