剑指 Offer 13. 机器人的运动范围 #
- 标签:深度优先搜索、广度优先搜索、动态规划
- 难度:中等
题目大意 #
描述:有一个 m * n
大小的方格,坐标从 (0, 0)
到 (m - 1, n - 1)
。一个机器人从 (0, 0)
处的格子开始移动,每次可以向上、下、左、右移动一格(不能移动到方格外),也不能移动到行坐标和列坐标的数位之和大于 k
的格子。现在给定 3
个整数 m
、n
、k
。
要求:计算并输出该机器人能够达到多少个格子。
说明:
- $1 \le n, m \le 100$。
- $0 \le k \le 20$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:广度优先搜索 #
先定义一个计算数位和的方法 digitsum
,该方法输入一个整数,返回该整数各个数位的总和。
然后我们使用广度优先搜索方法,具体步骤如下:
- 将
(0, 0)
加入队列queue
中。 - 当队列不为空时,每次将队首坐标弹出,加入访问集合
visited
中。 - 再将满足行列坐标的数位和不大于
k
的格子位置加入到队列中,继续弹出队首位置。 - 直到队列为空时停止。输出访问集合的长度。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(m \times n)$。其中 $m$ 为方格的行数,$n$ 为方格的列数。
- 空间复杂度:$O(m \times n)$。