《剑指|《剑指 Offer （第 2 版）》第 13 题（机器人的运动范围）《剑指Offer（第2版）》第13题：

第 13 题：机器人的运动范围
传送门：AcWing：机器人的运动范围，牛客网 online judge 地址。。

地上有一个行和列的方格，横纵坐标范围分别是和。
一个机器人从坐标的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于的格子。
请问该机器人能够达到多少个格子？
样例1：
【《剑指|《剑指 Offer （第 2 版）》第 13 题（机器人的运动范围）】输入：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 resdef __in_area(self, x, y, rows, cols): return 0 <= x < rows and 0 <= y < colsdef 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 0if threshold == 0: return 1directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] marked = [[False for _ in range(cols)] for _ in range(rows)]queue = [(0, 0)] res = 0while 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 resif __name__ == '__main__': k = 18 m = 40 n = 40 solution = Solution() result = solution.movingCount(k, m, n) print(result)