1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| # @Title: 机器人的运动范围 (机器人的运动范围 LCOF)
# @Author: 15816537946@163.com
# @Date: 2022-02-16 01:10:17
# @Runtime: 124 ms
# @Memory: 15.5 MB
def digitsum(n):
ans = 0
while n:
ans += n % 10
n //= 10
return ans
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
from queue import Queue
q = Queue()
q.put((0, 0))
s = set()
while not q.empty():
x, y = q.get()
if (x, y) not in s and 0 <= x < m and 0 <= y < n and digitsum(x) + digitsum(y) <= k:
s.add((x, y))
for nx, ny in [(x + 1, y), (x, y + 1)]:
q.put((nx, ny))
return len(s)
|