1、前言

2、思路

这道题一看就是 dfs 的思路来做，题目的要求是能到达多少个格子，应该算各个方向的总和且不能重复。但是是从左上角出发的，实际上就是向右和向下两个方向。

3、代码

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] array = new boolean[m][n];

        return dfs(array, 0, 0, k);
    }

    private int dfs(boolean[][] array, int i, int j, int k){
        if(i < 0 || i >= array.length || j < 0 || j >= array[0].length || array[i][j] || numSum(i) + numSum(j) > k){
            return 0;
        }

        array[i][j] = true;
        // 为什么只要两个方向，因为是从0开始的，只能向右或者向下才不会重复
        return dfs(array, i + 1, j, k)  + dfs(array, i, j + 1, k) + 1;
    }
    

    private int numSum(int n){
        int sum = 0;
        while(n > 0){
            sum += n % 10;
            n = n / 10;
        }
        return sum;
    }
}