题解 | #机器人的运动范围#

class Solution {
  private:
    int search(int x, int y, int threshold, vector<vector <int>>& matrix) {
        /*
            从当前节点出发，可以到的格子
        */
        if (x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size() ||
                matrix[x][y] || !underThreshold(x, y, threshold)) {
            return 0;
        }
        matrix[x][y] = 1;

        return 1 +  search(x + 1, y, threshold, matrix) +
               search(x - 1, y, threshold, matrix) +
               search(x, y + 1, threshold, matrix) +
               search(x, y - 1, threshold, matrix);
    }
    bool underThreshold(int x, int y, int threshold) {
        /*
            用于判断 x y 提取出来是否都小于阈值
        */
        int val = 0;
        while (x > 0) {
            val += x % 10;
            x = x / 10;
        }
        while (y > 0) {
            val += y % 10;
            y = y / 10;
        }
        if (val > threshold) return false;
        else return true;
    }

  public:
    int movingCount(int threshold, int rows, int cols) {
        // 似乎没有为空的情况要判断
        vector<vector <int>> matrix(rows,
                                    vector<int>(cols));  // 注意这个构造函数的写法
        vector<int> resultVec;

        // 先给matrix赋值, 0表示未到达
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = 0;
            }
        }

        return search(0, 0, threshold, matrix);
    }
};