机器人的运动范围

Leetcode Link: 面试题13. 机器人的运动范围 - 力扣（LeetCode）

题目

解法一：像回溯又不是回溯

思路： 没什么特别的，本题需要的注意的是

走过一个位置之后，如果从这个位置退出来，则不需要再把这个位置重置为没有走过，不然会重复计算。

但是也不能直接算里面有多少满足k的那个条件的格子，有可能满足条件的我们不能走到那里。

题解：

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        mask = [[0 for _ in range(n)] for _ in range(m)]
        res = 0
 
        def bkt(i, j):
            nonlocal res, k
            # 其实没有base case了，不合理都进不来
            res += 1
            direc = [(1, 0), (0, 1), (0, -1), (-1 ,0)]
            for d in direc:
                ni = i + d[0]
                nj = j + d[1]
                if 0 <= ni < m and 0 <= nj < n and mask[ni][nj] == 0 and self.check(str(ni)+str(nj), k):
                    mask[ni][nj] = 1
                    bkt(ni, nj)
                    # 注意这里不需要把mask[i][j]重置回0，避免重复计算。
        mask[0][0] = 1
        bkt(0, 0)
        return res
 
    # 检查当前坐标是不是可以走的
    # s 可以取 str(i)+str(j) 作为输入
    def check(self, s: str, k: int):
        lst = [int(x) for x in s]
        return sum(lst) <= k

启发和联系