《剑指 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)