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

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

解题思路1：DFS

机器人从(0,0)出发，只需向右和向下即可将所有的单元格遍历一次，遍历过程中加上限制条件。设置一个set用于存储遍历过的可行的单元格坐标，代码如下：
时间：\(O(MN)\)
空间：\(O(MN)\)

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        # 求数位和
        def ssum(a):
            res = 0
            while a:
                res += a % 10
                a //= 10
            return res

        def dfs(i, j):
            if not 0 <= i < m or not 0 <= j < n or ssum(i) + ssum(j) > k:   return 0
            if (i, j) not in visited:
                visited.add((i, j))
                return 1 + dfs(i+1, j) + dfs(i, j+1)
            else:
                return 0

        visited = set()
        return dfs(0, 0)

优质解答：（参考自K神）

思想基本相同，优化了取数位和的方法。

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def dfs(i, j, si, sj):
            if i >= m or j >= n or k < si + sj or (i, j) in visited: return 0
            visited.add((i,j))
            return 1 + dfs(i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj) + dfs(i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8)

        visited = set()
        return dfs(0, 0, 0, 0)