题目：

较难  通过率：24.82%  时间限制：1秒  空间限制：64M

知识点递归

描述

地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格   [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？

数据范围： 0≤threshold≤15  ，1≤rows,cols≤100 

进阶：空间复杂度 O(nm) ，时间复杂度 O(nm)

示例1

输入：

1,2,3

返回值：

3

示例2

输入：

0,1,3

返回值：

1

示例3

输入：

10,1,100

返回值：

29

说明：

[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种，后面的[0,29],[0,30]以及[0,31]等等是无法到达的      

示例4

输入：

5,10,10

返回值：

21

代码：

class Solution {
public:
    int movingCount(int threshold, int rows, int cols) {
        if(rows<=0 && cols <= 0) return 0;
        
        int visited[rows][cols];
        //初始化
        for(int i= 0; i<rows;i++)
            for(int j=0;j<cols;j++)
                visited[i][j] = 0;
        return countMax(threshold, rows, cols, 0, 0, &visited[0][0]);
    }
    
   int countMax(int threshold, int rows, int cols, int r, int c, int* visited){
        if(r < 0 || c < 0|| r >=rows|| c>= cols || *(visited+r*cols+c) == 1) return 0;
        if(!checkCondition(r, c, threshold)) return 0;
       
        *(visited+r*cols+c)  = 1;
        return 1 + countMax(threshold,  rows, cols, r-1, c, visited) 
            + countMax(threshold,  rows, cols, r+1, c, visited) 
            + countMax(threshold,  rows, cols, r, c-1, visited) 
            + countMax(threshold,  rows, cols, r, c+1, visited) ;
    }
    
    bool checkCondition(int row, int col, int threshold){
        int sum = 0;
        while(row){
            sum += row %10;
            row /= 10;
        }
        while(col){
            sum += col %10;
            col /= 10;
        }
        return sum <= threshold;
    }
    
    
};