題目描述
地上有一個(gè)m行和n列的方格。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開始移動(dòng)，每一次只能向左，右，上，下四個(gè)方向移動(dòng)一格，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。 例如，當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格（35,37），因?yàn)?+5+3+7 = 18。但是，它不能進(jìn)入方格（35,38），因?yàn)?+5+3+8 = 19。請(qǐng)問該機(jī)器人能夠達(dá)到多少個(gè)格子？

思路：這道題跟前一道題一樣，也是回溯法，分析題目，我們需要兩個(gè)全局變量：標(biāo)志數(shù)組和計(jì)數(shù)變量；需要一個(gè)函數(shù)來計(jì)算行坐標(biāo)和列坐標(biāo)的數(shù)位之和；終止條件包括三種情況：越界、重復(fù)、行坐標(biāo)和列坐標(biāo)的數(shù)位之和超過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:  # 重復(fù)路徑
        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