家居整理师将待整理衣橱划分为 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 <= 1000 <= cnt <= 20
解题思路：深度优先遍历
这道题，其实相比前面几道来说要简单的多，无非就是要多写一个 digit() 函数来获取数字的各数位之和罢了，剩下的就是深搜，遇到不符合条件的就停下来，当然一样需要使用 used 数组来防止重复访问！
class Solution {
private:
int res = 0; // 存放结果集
bool used[100][100]; // 防止重复访问
public:
int wardrobeFinishing(int m, int n, int cnt) {
dfs(m, n, cnt, 0, 0);
return res;
}
void dfs(int m, int n, int cnt, int i, int j)
{
// 递归函数出口
if(i == m || j == n || used[i][j] == true || digit(i) + digit(j) > cnt)
return;
res++;
used[i][j] = true;
dfs(m, n, cnt, i + 1, j);
dfs(m, n, cnt, i, j + 1);
}
// 获取数字的各数位之和
int digit(int n)
{
int ret = 0;
while(n != 0)
{
ret += (n % 10);
n /= 10;
}
return ret;
}
};