[剑指 Offer 第 2 版第 13 题] “机器人的运动范围”做题记录
[剑指 Offer 第 2 版第 13 题] “机器人的运动范围”做题记录
第 13 题:机器人的运动范围
传送门:AcWing:机器人的运动范围,牛客网 online judge 地址。。
地上有一个 m 行和 n 列的方格,横纵坐标范围分别是 0∼m−1 和 0∼n−1。
一个机器人从坐标 (0,0)的格子开始移动,每一次只能向左,右,上,下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
请问该机器人能够达到多少个格子?
样例1:
输入:k=7, m=4, n=5
输出:20
样例2:
输入:k=18, m=40, n=40
输出:1484
解释:当 k 为 18 时,机器人能够进入方格(35,37),因为 3+5+3+7 = 18。 但是,它不能进入方格(35,38),因为 3+5+3+8 = 19。
注意:
0<=m<=50
0<=n<=50
0<=k<=100
思路:使用广度优先搜索,注意不是深度优先搜索。
Python 代码:特别注意,mark 的时候,一定是放入队列的时候就 mark,不是等到出队的时候 mark,否则会出现很多重复
class Solution(object):
def __count_bit_sum(self, num):
res = 0
while num:
res += num % 10
num //= 10
return res
def __in_area(self, x, y, rows, cols):
return 0 <= x < rows and 0 <= y < cols
def movingCount(self, threshold, rows, cols):
"""
:type threshold: int
:type rows: int
:type cols: int
:rtype: int
"""
if threshold < 0 or rows == 0 or cols == 0:
return 0
if threshold == 0:
return 1
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
marked = [[False for _ in range(cols)] for _ in range(rows)]
queue = [(0, 0)]
res = 0
while queue:
top_x, top_y = queue.pop(0)
for direction in directions:
new_x = top_x + direction[0]
new_y = top_y + direction[1]
if self.__in_area(new_x, new_y, rows, cols) \
and not marked[new_x][new_y] \
and self.__count_bit_sum(new_x) + self.__count_bit_sum(new_y) <= threshold:
queue.append((new_x, new_y))
# 注意:应该写在这里,而不是 pop 出队列的时候
marked[new_x][new_y] = True
res += 1
return res
if __name__ == '__main__':
k = 18
m = 40
n = 40
solution = Solution()
result = solution.movingCount(k, m, n)
print(result)
作者:liweiwei1419
来源:https://liweiwei1419.github.io/sword-for-offer/
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程

本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com