家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。

整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。

请返回整理师 总共需要整理多少个格子。

示例 1：

输入：m = 4, n = 7, cnt = 5
输出：18

提示：

• 1 <= n, m <= 100
• 0 <= cnt <= 20

思路： DFS

1、定义digit函数，实现数字 x 的各数位之和。

2、因为不能重复整理，且题目没有定义二维数组只是给了二维数组的行列，因此我们需要自己定义一个二维数组用来标记哪些格子已经整理过，初始化为符号‘0’。

3、从头（[0][0]）开始DFS递归遍历

结束条件	i、j越界或该元素已经遍历过或digit函数不满足小于等于cnt。
递归工作	把该位置为‘1’，表示已经整理，继续向右和向下递归。
返回值	返回值为1加上向右和向下递归的结果。

4、注意：采用双层for循环的方法（行优先遍历二维数组所有元素）不可取，因为有一些格子虽然符合条件但是不可达，没有到达他的一条通路。

代码实现：

class Solution {
public:
    int digit(int a)
    {
        int sum = 0;
        while(a)
        {
            sum += a % 10;
            a /= 10;
        }
        return sum;
    }
    int dfs(int i, int j, int m, int n, int cnt,vector<vector<char>>& visited)
    {
        if(i < 0 || j < 0 || i >= m || j>= n || visited[i][j] != '0' || digit(i) + digit(j) > cnt )
            return 0;
        visited[i][j] = '1';
        return 1 + dfs(i + 1, j, m, n, cnt, visited) + dfs(i, j + 1, m, n, cnt, visited);
    }
    int wardrobeFinishing(int m, int n, int cnt) {
        vector<vector<char>> visited(m, vector<char>(n, '0'));
        return dfs(0, 0, m, n, cnt, visited);
    }
};