题目描述
地上有一个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