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

标签：深度优先搜索、广度优先搜索、动态规划
难度：中等

题目大意 #

有一个 m * n 大小的方格，坐标从 (0, 0) 到 (m - 1, n - 1)。一个机器人从 (0, 0) 处的格子开始移动，每次可以向上、下、左、右移动一格（不能移动到方格外），也不能移动到行坐标和列坐标的数位之和大于 k 的格子。现在给定 3 个整数 m、n、k。

要求：计算并输出该机器人能够达到多少个格子。

解题思路 #

使用广度优先搜索解决问题。

先定义一个计算数位和的方法 digitsum。然后通过队列进行广度优先搜索。

将 (0, 0) 加入队列，当队列不为空时，每次将队首坐标弹出，加入访问集合 visited 中。
再将满足行列坐标的数位和不大于 k 的格子坐标加入到队列中，继续弹出队首坐标。
直到队列为空时停止。输出访问集合的长度。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


import collections

class Solution:
    def digitsum(self, n: int):
        ans = 0
        while n:
            ans += n % 10
            n //= 10
        return ans

    def movingCount(self, m: int, n: int, k: int) -> int:
        queue = collections.deque()
        queue.append((0, 0))
        visited = set()

        while queue:
            x, y = queue.popleft()
            if (x, y) not in visited and self.digitsum(x) + self.digitsum(y) <= k:
                visited.add((x, y))
                for dx, dy in [(1, 0), (0, 1)]:
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < m and 0 <= ny < n:
                        queue.append((nx, ny))
        return len(visited)