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

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

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

题目大意 #

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

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

说明

  • $1 \le n, m \le 100$。
  • $0 \le k \le 20$。

示例

1
2
3
4
5
6
输入m = 2, n = 3, k = 1
输出3


输入m = 3, n = 1, k = 0
输出1

解题思路 #

思路 1:广度优先搜索 #

先定义一个计算数位和的方法 digitsum,该方法输入一个整数,返回该整数各个数位的总和。

然后我们使用广度优先搜索方法,具体步骤如下:

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

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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([(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)

思路 1:复杂度分析 #

  • 时间复杂度:$O(m \times n)$。其中 $m$ 为方格的行数,$n$ 为方格的列数。
  • 空间复杂度:$O(m \times n)$。
本站总访问量  次  |  您是本站第  位访问者