[剑指 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。

注意:

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/