class Solution {
private:
    int res = 0;
    int get(int x) {
        int ans = 0;
        while(x) {
            ans += x % 10;
            x /= 10;
        }
        return ans;
    }
    void dfs(vector<vector<bool>> &vis, int x, int y, int m, int n, int k) {
        // 注意判断条件中vis[x][y]一定要写在后面
        if(x < 0 || x >= m || y < 0 || y >= n || get(x)+get(y) > k || vis[x][y]) return;
        ++ res;
        vis[x][y] = true;

        dfs(vis, x + 1, y, m, n, k);
        dfs(vis, x, y + 1, m, n, k);

    }
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> vis(m, vector<bool>(n));
        dfs(vis, 0, 0, m, n, k);
        return res;
    }
};

class Solution {
private:
    int get(int x) {
        int ans = 0;
        while(x) {
            ans += x % 10;
            x /= 10;
        }
        return ans;
    }
public:
    int movingCount(int m, int n, int k) {
        // 注意前面要加一个判断，因为在队列中至少要入队一个元素
        // 默认入队的{0, 0}满足k>0
        if(k == 0) return 1;
        queue<pair<int, int>> que;
        vector<vector<bool>> vis(m, vector<bool>(n));
        // 默认(0,0)已经入队
        int res = 1;
        que.push({0, 0});
        int dx[2] = {1, 0};
        int dy[2] = {0, 1};
        vis[0][0] = true;
        while(!que.empty()){
            auto [x, y] = que.front();
            que.pop();
            for(int i = 0; i < 2;  i++ ) {
                int tx = x + dx[i], ty = y + dy[i];
                if(tx >= 0 && tx < m && ty >= 0 && ty < n && get(tx) + get(ty) <= k && !vis[tx][ty]) {
                    que.push({tx, ty});++ res;
                    vis[tx][ty] = true;
                }
            }
        }
        return res;
    }
};