【剑指offer】机器人的运动范围（python）

回溯是DFS的特例，每次搜索需要设置本次搜索的局部状态，并在本次搜索结束后清除状态，这里就是 mark[r][c]=True，标记这里已经遍历了。
和“矩阵中的路径”思路差不多，这个简单些。

# -*- coding:utf-8 -*-
class Solution:
    next = [[0,1],[0,-1],[1,0],[-1,0]]
    rows = 0
    cols = 0
    count = 0
    def movingCount(self, threshold, rows, cols):
        # write code here
        self.rows = rows
        self.cols = cols
        self.count = 0
        digitSum = self.initDigitSum()
        mark = [[False for i in range(self.cols)] for j in range(self.rows)]
        self.dfs(digitSum,mark,0,0,threshold)
        return self.count
    def dfs(self, digitSum, mark, r, c, threshold):
        if r = self.rows or c = self.cols or mark[r][c]:
            return
        mark[r][c] = True
        if digitSum[r][c] > threshold:
            return
        self.count += 1
        for i in self.next:
            self.dfs( digitSum,mark, r+i[0], c+i[1],threshold)
    def initDigitSum(self):
        digitSumOne = [0 for i in range(max(self.rows,self.cols))]
        for i in range(len(digitSumOne)):
            n = i
            while n > 0:
                digitSumOne[i] += n %10
                n /= 10
        digitSum = [[0 for i in range(self.cols)] for j in range(self.rows)]
        for i in range(self.rows):
            for j in range(self.cols):
                digitSum[i][j] = digitSumOne[i] + digitSumOne[j]
        return digitSum