难度：★★★☆☆
类型：数组
方法：深度优先搜索or宽度优先搜索

题目

力扣链接请移步【本题传送门】
更多力扣题解请移步【力扣-剑指offer目录】

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

示例 2：

输入：m = 3, n = 1, k = 0
输出：1
提示：

1 <= n,m <= 100
0 <= k <= 20

解答

方案1：深度优先搜索

我们把一些功能块封装成函数，便于理解和使用：

neighbours(r, c)：用于获取某个点处的所有相邻合法点（不越界）坐标；
digit_sum(n)：计算某个数字的各位数字之和；
can_arrive(r, c)：判断某个点按照题目要求是否可到达；

其他注意事项：

• 遍历过程中使用集合footprint来记录走过的点，避免重复遍历造成死循环；
• 深度优先搜索函数dfs使用递归实现，开头写清终止条件，并在通过校验后对相邻点进行遍历递归；
• 按照题目要求，最后返回足迹集合的长度即可。

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:

        def neighbours(r, c):
            """
            获取(r, c)所有合法相邻位置坐标
            """
            for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    yield nr, nc

        def digit_sum(n):
            """
            计算数字n各个位置之和
            """
            s = 0
            while n:
                n, r = divmod(n, 10)
                s += r
            return s

        def can_arrive(r, c):
            """
            判断(r, c)位置是否可以到达
            """
            return digit_sum(r) + digit_sum(c) <= k

        footprint = set()           # 足迹集合
        def dfs(r, c):
            if (r, c) in footprint or not can_arrive(r, c):
                return
            footprint.add((r, c))
            for nr, nc in neighbours(r, c):
                dfs(nr, nc)

        dfs(0, 0)
        # print(footprint)
        return len(footprint)           # 所有可以到达的位置的个数



s = Solution()
print(s.movingCount(2, 3, 1))
print(s.movingCount(3, 1, 0))

方案2：宽度优先搜索

我们把上面所述的算法用宽度优先搜索改写，使用队列就可以实现。

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:

        def neighbours(r, c):
            """
            获取(r, c)所有合法相邻位置坐标
            """
            for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    yield nr, nc

        def digit_sum(n):
            """
            计算数字n各个位置之和
            """
            s = 0
            while n:
                n, r = divmod(n, 10)
                s += r
            return s

        def can_arrive(r, c):
            """
            判断(r, c)位置是否可以到达
            """
            return digit_sum(r) + digit_sum(c) <= k

        queue = [(0, 0)]
        footprint = set()
        while queue:
            r, c = queue.pop(0)
            if (r, c) in footprint or not can_arrive(r, c):
                continue
            footprint.add((r, c))
            for nr, nc in neighbours(r, c):
                queue.append((nr, nc))

        return len(footprint)           # 所有可以到达的位置的个数


s = Solution()
print(s.movingCount(2, 3, 1))
print(s.movingCount(3, 1, 0))

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步【力扣面试题解析】