题解 | #矩阵中的路径#

public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        return dfs(threshold,0,0,rows,cols,new boolean[rows][cols]) ;
    }
    
    /*
    从坐标i , j出发所能到达最多的格子数
    */
    public int dfs(int threshold , int i , int j , int rows , int cols ,boolean isvisit[][]) {
        if(i < 0 || i >= rows || j < 0 || j >= cols) {
            return 0 ;
        }
        if(isvisit[i][j]) {
            return 0 ;
        }
        if(bitSum(i,j) > threshold) {
            return 0 ;
        }
        isvisit[i][j] = true ;
        int[] maxTemp = new int[4] ;
        maxTemp[0] = dfs(threshold,i-1,j,rows,cols,isvisit) ;
        maxTemp[1] = dfs(threshold,i+1,j,rows,cols,isvisit) ;
        maxTemp[2] = dfs(threshold,i,j-1,rows,cols,isvisit) ;
        maxTemp[3] = dfs(threshold,i,j+1,rows,cols,isvisit) ;
        int sum = 0 ;
        //所有路径中经过的格子之和
        for(int k = 0 ; k < 4 ; k ++) {
            sum += maxTemp[k] ;
        }
        //isvisit[i][j] = false ;  这里不必还原现场，因为需求是统计及其所有路径中能到的格子总数，
        //每个格子只能计算一次，如果还原现场则每个格子可能会被计算多次
        return sum+1 ;
    }
    //求坐标的数位之和
    public int bitSum(int r , int c) {
        int sum = 0 ;
        while(r != 0) {
            sum += (r % 10 );
            r /= 10 ;
        }
        while(c != 0) {
            sum += (c % 10) ;
            c /= 10 ;
        }
        return sum ;
    }
}