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

class Solution:
    def __init__(self):
        self.num = 0
    # 计算[i, j]位数之和
    def cal(self, i, j):
        lst_i = [int(x) for x in str(i)]
        lst_j = [int(y) for y in str(j)]
        return sum(lst_i)+sum(lst_j)
    # 深度优先搜索
    def dfs(self, i, j, rows, cols, lst, k):
        # 是否数组越界
        if i < 0 or j < 0 or i >= rows or j >= cols:
            return
        # 是否访问过
        if lst[i][j] == -1:
            return
        # 是否越值
        if self.cal(i, j) > k:
            return
        self.num +=1
        lst[i][j] = -1
        self.dfs(i+1, j, rows, cols, lst, k)
        self.dfs(i-1, j, rows, cols, lst, k)
        self.dfs(i, j+1, rows, cols, lst, k)
        self.dfs(i, j-1, rows, cols, lst, k)
    def movingCount(self , threshold: int, rows: int, cols: int) -> int:
        if threshold < 0:
            return 1
        lst = [[0 for _ in range(cols)] for _ in range(rows)]
        self.dfs(0, 0, rows, cols, lst, threshold)
        return self.num