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

#include <algorithm>
#include <string>
#include <vector>
class Solution {
public:
    int res=0; 
    int get_str_num(string a){
        int sum=0;
        for(char c : a){
            if (isdigit(c)) {
                int digit = c - '0';
                sum += digit;
            }
        }
        return sum;
        
    }
    
    int max_path_count(int threshold, int rows, int cols, int i, int j, vector<vector<bool>>& matrix){
        
        if((get_str_num(to_string(i))+get_str_num(to_string(j)))>threshold || 
            i<0||i>=rows||j<0||j>=cols|| matrix[i][j]==true){
            return 0;
        }
        res += 1;
        matrix[i][j] = true;
        int a = max_path_count(threshold, rows, cols, i+1,j,matrix);
        int b = max_path_count(threshold, rows,   cols, i-1,j, matrix);
        int c = max_path_count(threshold, rows, cols, i,j-1, matrix);
        int d = max_path_count(threshold, rows, cols, i,j+1, matrix);
        return 0;
    } 
    int movingCount(int threshold, int rows, int cols) {
        if (threshold<=0) {
            return 1;
        }
        vector<vector<bool>> matrix(rows, vector<bool>(cols, false));
        int num = max_path_count(threshold, rows, cols, 0,0, matrix);
        return res;
    }
};

采用深度优先搜索算法，先按照深度把一个分支走到头，再向上一级回溯，直到走完整个矩阵。