剑指 Offer 13. 机器人的运动范围

分析

这题和之前做过的12有不同之处。12是可以从每一个点遍历，而本题只能从原点遍历。
注意，这题的关键之处在于求和。把上下左右的和都加起来，这才是真正的和。

DFS法

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        return self.dfs(m, n, 0, 0, k, 0, set())
    def dfs(self, m, n, i, j, k, r, visited):
    	# r代表当前节点和相邻可联通节点可以贡献的值
        if self.get_sum(i) + self.get_sum(j) > k:
            return r
        r += 1
        ori_r = r
        visited.add((i, j))
        if i-1>=0 and (i-1, j) not in visited:
            r += self.dfs(m, n, i-1, j, k, 0, visited)
        if i+1<m and (i+1, j) not in visited:
            r += self.dfs(m, n, i+1, j, k, 0, visited)
        if j-1>=0 and (i, j-1) not in visited:
            r += self.dfs(m, n, i, j-1, k, 0, visited)
        if j+1<n and (i, j+1) not in visited:
            r += self.dfs(m, n, i, j+1, k, 0, visited)
        return r
    def get_sum(self, nums):
    	# 抽象出求和函数, 减少代码量
        res = 0
        while nums:
            res += nums%10
            nums//=10
        return res