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

//
//  s_20.cpp
//  swordOffer
//
//  Created by YangKi on 2017/2/14.
//  Copyright © 2017年 yangqi916. All rights reserved.
//

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

class Solution {
    
    int core(int threshold, int rows, int cols, int curRow, int curCol, vector<vector<bool>>& visited)
    {
        int cnt = 0;
        
        if(check(threshold, rows, cols, curRow, curCol, visited)) {
            visited[curRow][curCol] = true;
            
            cnt = 1 + core(threshold, rows, cols, curRow + 1, curCol, visited)
                    + core(threshold, rows, cols, curRow - 1, curCol, visited)
                    + core(threshold, rows, cols, curRow, curCol + 1, visited)
                    + core(threshold, rows, cols, curRow, curCol - 1, visited);
            
        }
        
        return cnt;
    }
    
    bool check(int threshold, int rows, int cols, int curRow, int curCol, vector<vector<bool>>& visited)
    {
        if(curRow >= 0 && curRow < rows
           && curCol >= 0 && curCol < cols
           && getDigitSum(curRow) + getDigitSum(curCol) <= threshold
           && visited[curRow][curCol] == false)
        {
            return true;
        }
        else
            return false;
    }
    
    int getDigitSum(int num) {
        int sum = 0;
        
        while (num) {
            sum += (num % 10);
            num /= 10;
        }
        
        return sum;
    }
    
public:
    int movingCount(int threshold, int rows, int cols)
    {
        vector<vector<bool>>visited(rows, vector<bool>(cols, false));
        
        int cnt = core(threshold, rows, cols, 0, 0, visited);
        
        return cnt;
    }
};