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];
       // for(int row = 0; row < rows; row++){
        //    for(int col = 0; col < cols; col++){
        //        if( movingCountCore(threshold,row,rows,,col,cols,visited)){
        //            
        //        }
       //     }
       // }
        
        int count = movingCountCore(threshold,0,rows,0,cols,visited);
        return count;
    }
   
    public static int movingCountCore(int threshold, int row,int rows, int col, int cols,boolean[] visited){
        
        int res = 0;
        if(row>=0 && row<rows && col>=0 && col<cols && visited[row*cols+col]==false){
            if(splitNum(row) + splitNum(col) <= threshold){
                visited[row*cols+col]=true;
                res = 1+movingCountCore(threshold,row+1,rows, col,cols,visited)
                    +movingCountCore(threshold,row-1,rows, col,cols,visited)
                    +movingCountCore(threshold,row,rows, col+1,cols,visited)
                    +movingCountCore(threshold,row,rows, col-1,cols,visited);
            }
            
        }
        return res;
        
    }
    public static int splitNum(int number){
        int sum = 0;
        while(number >0){
            sum+=number%10;
            number =  number/10;
        }
        return sum;
    }
}