剑指offer 机器人的运动范围

思想：回溯
实现：

class Solution_:
    def movingCount(self, threshold, rows, cols):
        # write code here
        if rows < 1 or cols < 1 or threshold <= 0:
            return 0

        self.hash = {}
        self.cnt = 0
        def DFS(i, j):
            if check(i, j):
                self.cnt += 1
                self.hash[(i, j)] = 1
                DFS(i - 1, j)
                DFS(i + 1, j)
                DFS(i, j + 1)
                DFS(i, j - 1)

        def check(i, j):
            def getSum(num):
                res = 0
                while num:
                    res += num % 10
                    num = num // 10
                return res

            return 0 <= i < rows and 0 <= j < cols and (i, j) not in self.hash and getSum(i) + getSum(j) <= threshold

        DFS(0, 0)
        return self.cnt