机械人运动这类问题在做题的过程中遇到过好几次,
大概类型就是给定一个初始位置,可以往多个方向走(一般是2个,即右下),
有时候是4个方向(上下左右),
然后求到右下角的最小路径,这类问题一般是采用动态规划来做,
有时候可能会出现阻碍物,
但机器人这道题就简化了很多,直接看题吧。
机器人的运动范围
地上有一个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:
1 | 输入:m = 2, n = 3, k = 1 |
示例 2:
1 | 输入:m = 3, n = 1, k = 0 |
提示:
1 <= n,m <= 100
0 <= k <= 20
解题思路
题目和我们一开始分析的那样,
机器人的位置在m行n列方格的左上角开始,
但目标不是右下角了,而是移动当坐标的数位之和大于k后就不能继续移动了,
这道题有个隐藏的条件,
题目说可以上下左右移动,我觉得有一定的误导,这道题只要两个方向就可以了,
因为机器人的初始位置在左上角,只要向右或者向下两个方向就行了,
对于每个点,只要满足三个条件,就可以继续进行两个方向的选择,
- 该点还没被访问过
- 该点的数位之和小于等于k
- 该点不在边界
对于该点是否被访问,我们可以用一个boolean型的数组记录该点的访问状态,被访问后就变为true,
对于该点的数位之和,我们可以写一个函数专门计算数位的和,
1 | //传入坐标信息 |
对该点是否在边界,如果在右边界,就只能向下运动,如果在下边界,就只能向右运动,其他边界无需考虑,
本题可以使用深度优先搜索和广度优先搜索来做,
深度优先搜索就是对每一个方向都递归前进,
广度优先搜索要采用队列来记录合格的点信息,还需要对方格进行抽象坐标化,
具体我们看代码。
代码
- 深度优先搜索
1 | class Solution { |
- 广度优先搜索
1 | class Solution { |
整理于2020.4.9