题目描述 [机器人的运动范围]
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
解题思路
DFS 额 主要是退出的条件要细心一点！
代码
class Solution {
public:
int movingCount(int threshold, int rows, int cols){
vector<vector<int> > mat(rows, vector<int>(cols, 0));
if(threshold==0 || rows==0 || cols==0) return 0;
return cal_num(mat, threshold, rows, cols, 0, 0);
}
int cal_num(vector<vector<int> > &mat, int threshold, int rows, int cols, int i, int j){
if(i<0||j<0||i>=rows||j>=cols||!isOk(threshold,i,j)||mat[i][j]==1) return 0;
mat[i][j] = 1;
return cal_num(mat, threshold, rows, cols, i-1, j) +
cal_num(mat, threshold, rows, cols, i+1, j)+
cal_num(mat, threshold, rows, cols, i, j-1)+
cal_num(mat, threshold, rows, cols, i, j+1)+1;
}
bool isOk(int threshold, int i, int j){
int sum=0;
while(i){
sum += i%10;
i /= 10;
}
while(j){
sum += j%10;
j /= 10;
}
return sum<=threshold ? true:false;
}
};