AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

AcWing 24. 机器人的运动范围    原题链接    简单

作者: 作者的头像   Clean_up_the_stupid_incra ,  2023-05-26 21:07:52 ,  所有人可见 ,  阅读 41


2


首先,机器人的移动只能是横纵坐标加减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 集合用于标记已经访问过的坐标,避免重复访问。

0 评论

你确定删除吗?

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息