机器人的运动范围

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

思路：这道题跟前一道题一样，也是回溯法，分析题目，我们需要两个全局变量：标志数组和计数变量；需要一个函数来计算行坐标和列坐标的数位之和；终止条件包括三种情况：越界、重复、行坐标和列坐标的数位之和超过k，然后流程和上一道题相同。AC代码如下：

def __init__(self):
    self._dict = {}
    self.count = 0
def get_sum(self, i ,j):
    num = 0
    while i:
        temp = i % 10
        i = i / 10
        num += temp
    while j:
        temp = j % 10
        j = j / 10
        num += temp
    return num
def dfs(self, matrix, k, i, j):

    if not (0 <= i< len(matrix) and 0 <= j < len(matrix[0])):  # 越界
        return
    if self.get_sum(i, j) > k:  # 大于k
        return
    if self._dict.get((i,j)) is not None:  # 重复路径
        return
    self._dict[(i,j)] = 1
    self.count += 1
    # 向上下左右寻找
    self.dfs(matrix,k,i+1,j)
    self.dfs(matrix,k,i-1,j)
    self.dfs(matrix,k,i,j+1)
    self.dfs(matrix,k,i,j-1)
def movingCount(self, threshold, rows, cols):
    # write code here
    x = [[1 for i in range(cols)] for j in range(rows)]
    self.dfs(x, threshold, 0, 0)
    return self.count