bfs

class Solution {
public:
    int movingCount(int threshold, int rows, int cols) {
        if (rows == 0|| cols == 0) return 0;
        vector<vector<bool>> matrix(rows, vector<bool>(cols));
        int dx[4] {0, 0, 1, -1}, dy[4] {1, -1, 0, 0};
        queue<pair<int, int>> q {{{0, 0}}};
        matrix[0][0] = true;
        int res = 1; 

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();

            for (int i=0; i<4; i++) {
                int new_x = x+dx[i], new_y = y+dy[i];
                if (isLegit(new_x, new_y, threshold) && 
                    new_x >= 0 && new_x < rows && new_y >= 0 && 
                    new_y < cols && !matrix[new_x][new_y]) {

                    matrix[new_x][new_y] = true;
                    res ++;
                    q.push({new_x, new_y});
                }
            }
        }

        return res;
    }

    bool isLegit(int i, int j, int threshold) {
        int sum = 0;
        while(i) {
            sum += i%10;
            i/=10;
        }
        while(j) {
            sum += j%10;
            j/=10;
        }
        return threshold >= sum;
    }
};

dfs

class Solution {
public:
    vector<vector<bool>> matrix;
    int mthreshold;
    int dx[4] {0, 0, 1, -1}, dy[4] {1, -1, 0, 0};
    int mcol, mrow;

    int movingCount(int threshold, int rows, int cols) {
        if (rows == 0|| cols == 0) return 0;
        mcol = cols; mrow = rows;
        matrix = vector<vector<bool>>(rows, vector<bool>(cols, false));
        mthreshold = threshold;

        return dfs(0, 0);
    }

    int dfs(int x, int y) {
        if (!isLegit(x, y) || matrix[x][y]) return 0;
        int sum = 1;
        matrix[x][y] = true;
        for (int i=0; i<4; i++) {
            int new_x = x+dx[i], new_y = y+dy[i];

            if (new_x >= 0 && new_x < mrow && 
                new_y >= 0 && new_y < mcol && !matrix[new_x][new_y]) {
                    sum += dfs(new_x, new_y);
                }
        }
        return sum;
    }

    bool isLegit(int i, int j) {
        int sum = 0;
        while(i) {
            sum += i%10;
            i/=10;
        }
        while(j) {
            sum += j%10;
            j/=10;
        }
        return mthreshold >= sum;
    }
};