地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

 

java:

1 public class Solution { 2     private int rows ; 3     private int cols ; 4     private int cnt = 0 ; 5     private int threshold ; 6     private static final int[][] next = {
   {0,1} , {0,-1} , {1,0} , {-1,0}} ; 7     private int[][] digitSum ; 8     public int movingCount(int threshold, int rows, int cols) 9     {10         this.threshold = threshold ;11         this.rows = rows ;12         this.cols = cols ;13         init() ;14         boolean[][] mark = new boolean[rows][cols] ;15         dfs(0,0,mark) ;16         return cnt ;17     }18     19     private void dfs(int r, int c , boolean[][] mark){20         if (r < 0 || r >= rows || c < 0 || c >=cols || mark[r][c])21             return ;22         mark[r][c] = true ;23         if (digitSum[r][c] > threshold)24             return ;25         cnt++ ;26         for(int[] n : next){27             dfs(r+n[0],c+n[1],mark) ;28         }29     }30     31     private void init(){32         int[] digitOne = new int[Math.max(rows,cols)] ;33         for(int i = 0 ; i < digitOne.length ; i++){34             int n = i ;35             while(n > 0){36                 digitOne[i] += n%10 ;37                 n/=10 ;38             }39         }40         digitSum = new int[rows][cols] ;41         for(int i = 0 ; i < rows ; i++){42             for(int j = 0 ; j < cols ; j++){43                 digitSum[i][j] = digitOne[i] + digitOne[j] ;44             }45         }46     }47 }