地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。 一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。 但是不能进入行坐标和列坐标的数位之和大于 k 的格子。 请问该机器人能够达到多少个格子？ 样例1 输入：k=7, m=4, n=5 输出：20 样例2 输入：k=18, m=40, n=40 输出：1484 解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。 但是，它不能进入方格（35,38），因为3+5+3+8 = 19。 注意: 0<=m<=50 0<=n<=50 0<=k<=100
思路： 回溯法！！！ C++代码：
class Solution { public: bool numSum(int now_row, int now_col, int threshold){ int sum_pos = 0; while(now_row){ sum_pos += now_row % 10; now_row /= 10; } while(now_col){ sum_pos += now_col % 10; now_col /= 10; } if(sum_pos <= threshold){ return true; }else{ return false; } } int count_bin(int now_row, int now_col, int rows, int cols, int threshold, vector<vector<int>>& visited){ int count = 0; bool num_sum = numSum(now_row, now_col, threshold); if(now_row >= 0 && now_row < rows && now_col >=0 && now_col < cols && !visited[now_row][now_col] && num_sum){ visited[now_row][now_col] = 1; count = 1 + count_bin(now_row + 1, now_col, rows, cols, threshold, visited) + count_bin(now_row - 1, now_col, rows, cols, threshold, visited) + count_bin(now_row, now_col + 1, rows, cols, threshold, visited) + count_bin(now_row, now_col - 1, rows, cols, threshold, visited); } return count; } int movingCount(int threshold, int rows, int cols) { if(threshold < 0 || rows < 1 || cols < 1){ return 0; } int now_row = 0; int now_col = 0; vector<vector<int>> visited; for(int i = 0; i < rows; i++){ visited.push_back(vector<int>(cols, 0)); } int count = count_bin(0, 0, rows, cols, threshold, visited); return count; } };python代码（超时）：
class Solution(object): def numSum(self, now_row, now_col, threshold): pos_sum = 0 while now_row: pos_sum += now_row % 10 now_row = now_row // 10 while now_col: pos_sum += now_col % 10 now_col = now_col // 10 if pos_sum <= threshold: return True else: return False def countSum(self, now_row, now_col, rows, cols, threshold, visited): count = 0 num_sum = self.numSum(now_row, now_col, threshold) if 0 <= now_row < rows and 0 <= now_col < cols and not visited[now_row][now_col] and num_sum: visited[now_row][now_col] = 1 count = 1 + self.countSum(now_row + 1, now_col, rows, cols, threshold, visited) + self.countSum(now_row - 1, now_col, rows, cols, threshold, visited) + self.countSum(now_row, now_col + 1, rows, cols, threshold, visited) + self.countSum(now_row, now_col - 1, rows, cols, threshold, visited) return count def movingCount(self, threshold, rows, cols): """ :type threshold: int :type rows: int :type cols: int :rtype: int """ if threshold < 0 or rows <= 0 or cols <= 0: return 0 visited = [[0] * cols for row in range(rows)] count_sum = self.countSum(0, 0, rows, cols, threshold, visited) return count_sum