题解 | #机器人的运动范围#

（解题思路参考的是几位朋友的，侵权联系删）
DFS深度优先搜索：
（1）首先说一下终止条件：
①行数i（从0开始）大于等于rows；
②列数j（从0开始）大于等于cols；
③行数i与列数j的各位数的和大于threshold；
④该位置已经走过，即（i，j）in res。res中记录了走过点的坐标
（2）思路：
先朝下搜到底，直到遇到终止条件；再向右搜索，再次碰到终止条件；回退到上一个节点向下搜索，不行再向右搜索，还是不行就在返回上上个节点...（递归）
（3）代码
class Solution:

def movingCount(self, threshold, rows, cols):
    # write code here
    def calSum(num):
        '''rc:作用是计算各位数值之和，简单一看'''
        sum = 0
        while num:
            sum += num % 10  #取余数
            num = num // 10  #整除，向下取整
        return sum

    def dfs(i,j,k):
        '''rc:主要递归函数'''
        if i>=rows or j>=cols or (i,j) in res or calSum(i)+calSum(j)>k:   #rc:四个终止条件
            return
        else:
            res.add((i,j)) #rc:记录走过的路径
            dfs(i+1,j,k) #rc:向下搜索
            dfs(i,j+1,k) #rc:向右搜索
            return
    res = set()
    dfs(0,0,threshold)
    return len(res)