private static final int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

private int cols;

private int rows;

private int cnt = 0;

private int threshold;

private int[][] digitSum;

public int movingCount(int threshold,int rows,int cols)

{

this.cols = cols;

this.rows = rows;

this.threshold = threshold;

initDigitSum();

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

dfs(marked,0,0);

return cnt;

}

private void dfs(boolean[][] marked, int r, int c) {

if(r<0||r>=rows||c<0||c>=cols||marked[r][c])

{

return;

}

marked[r][c] = true;

if(this.digitSum[r][c] > this.threshold)

{

return;

}

cnt++;

for(int[] n : next)

{

dfs(marked,r+n[0],c+n[1]);

}

}

private void initDigitSum() {

int[] digitSumone = new int[Math.max(rows,cols)];

for(int i =0;i<digitSumone.length;i++)

{

int n = i;

while(n>0)

{

digitSumone[i]+=n%10;

n = n/10;

}

}

this.digitSum = new int[rows][cols];

for (int i = 0;i<rows;i++)

{

for (int j = 0;j<cols;j++)

{

this.digitSum[i][j] = digitSumone[i]+digitSumone[j];

}

}

}