Solution

class Solution {
public:
    int movingCount(int threshold, int rows, int cols) {
        int res = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (getValue(i, j, threshold)) res++;
                else if (rows == 1 || cols == 1)    //!适用于行或列为 1 时，及时退出
                    return res;
            }
        }
        return res;
    }
    
    bool getValue(int r, int c, int threshhold) {
        int sum = 0;
        while (r != 0) {
            sum += r % 10;
            r = r / 10;
        }
        while (c != 0) {
            sum += c % 10;
            c = c / 10;
        }
        return sum <= threshhold;
    }
};

• 完全回溯

class Solution {
public:
    int movingCount(int threshold, int rows, int cols) {
        if (rows < 1 || cols < 1) return 0;
        visited = vector<vector<bool>>(rows, vector<bool>(cols, false));
        int res = backtrack(threshold, rows, cols, 0, 0);
        return res;
    }
private:
    vector<vector<bool>> visited;
    
    int backtrack(int threshold, int rows, int cols, int r, int c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols
            || !getValue(r, c, threshold) || visited[r][c] == true) {
            return 0;
        }

        visited[r][c] = true;
        
        // 因为从 (0,0) 开始，只需要判断向右和向下的情况
        return 1 + backtrack(threshold, rows, cols, r+1, c) + backtrack(threshold, rows, cols, r, c+1);
    }
    
    bool getValue(int r, int c, int threshhold) {
        int sum = 0;
        while (r != 0) {
            sum += r % 10;
            r = r / 10;
        }
        while (c != 0) {
            sum += c % 10;
            c = c / 10;
        }
        return sum <= threshhold;
    }
};