首先,机器人的移动只能是横纵坐标加减1,这提示我们使用 BFS 算法求解最大可达到格子数。
其次,需要注意不能进入行坐标和列坐标的数位之和大于 k 的格子。可以写一个函数 getSum 来计算一个数的所有数位之和,并在 BFS 过程中判断当前格子对应的坐标的数位之和是否超过了 k。
最后,遍历完后,通过记录访问过的坐标数量返回最大可达到的格子数。
Python 代码实现:
python
import queue
# 计算一个数的各个数字之和
def getSum(num):
s = 0
while num > 0:
s += num % 10
num //= 10
return s
def movingCount(k: int, m: int, n: int) -> int:
visited = set() # 存储访问过的坐标
q = queue.Queue() # 队列保存待访问的坐标
q.put((0, 0)) # 将起点添加到队列中
visited.add((0, 0)) # 标记起点为已访问
cnt = 1 # 统计可以到达的格子数,起点已经访问过了
dx = [0, 1, 0, -1] # 横向移动的方向数组
dy = [1, 0, -1, 0] # 纵向移动的方向数组
while not q.empty():
x, y = q.get()
for i in range(4):
newx, newy = x + dx[i], y + dy[i]
if 0 <= newx < m and 0 <= newy < n and (newx, newy) not in visited and getSum(newx) + getSum(newy) <= k:
q.put((newx, newy))
visited.add((newx, newy))
cnt += 1
return cnt
其中 visited 集合用于标记已经访问过的坐标,避免重复访问。