1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 13 题] “机器人的运动范围”做题记录

[剑指 Offer 第 2 版第 13 题] “机器人的运动范围”做题记录

第 13 题:机器人的运动范围

传送门:AcWing:机器人的运动范围牛客网 online judge 地址。。

地上有一个 m 行和 n 列的方格,横纵坐标范围分别是 0∼m−10∼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。

注意:

  1. 0<=m<=50
  2. 0<=n<=50
  3. 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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 13 题] “机器人的运动范围”做题记录

链接:https://www.javajike.com/article/3264.html

« [剑指 Offer 第 2 版第 12 题] “矩阵中的路径”做题记录
[剑指 Offer 第 2 版第 14 题] “剪绳子”做题记录»

相关推荐

QR code