家居整理师将待整理衣橱划分为 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

整理规则是只能向右或向下移动，所以假如 i,j 不需整理，则不再考虑 i+1，j 和i，j+1

我们可以使用dfs或bfs，对可移动到的每个格子进行判断

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        int ans = 0;
        queue<pair<int, int>> q;
        vector<vector<bool>> vis(m, vector<bool>(n));
        q.push({0, 0});
        while (!q.empty()) {
            int i = q.front().first;
            int j = q.front().second;
            q.pop();
            if (i >= m || j >= n)
                continue;
            if (sum(i) + sum(j) > cnt)
                continue;
            if (vis[i][j])
                continue;
            vis[i][j] = true;
            ans++;
            q.push({i + 1, j});
            q.push({i, j + 1});
        }
        return ans;
    }
    int sum(int x) {
        int s = 0;
        while (x != 0) {
            s += x % 10;
            x /= 10;
        }
        return s;
    }
};

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int ans = 0;
    int m, n, cnt;
    int wardrobeFinishing(int m, int n, int cnt) {
        this->m = m;
        this->n = n;
        this->cnt = cnt;
        vector<vector<bool>> vis(m, vector<bool>(n));
        dfs(0, 0, vis);
        return ans;
    }
    int sum(int x) {
        int s = 0;
        while (x != 0) {
            s += x % 10;
            x /= 10;
        }
        return s;
    }
    void dfs(int i, int j, vector<vector<bool>> &vis) {
        if (i >= m || j >= n)
            return;
        if (sum(i) + sum(j) > cnt)
            return;
        if (vis[i][j])
            return;
        vis[i][j] = true;
        ans++;
        dfs(i + 1, j, vis);
        dfs(i, j + 1, vis);
    }
};