AcWing 24. 机器人的运动范围
原题链接
简单
作者:
buchiyu
,
2021-05-11 10:28:09
,
所有人可见
,
阅读 237
宽搜
class Solution(object):
def get_single_sum (self, x):
count = 0
while x :
count += x % 10
x //= 10
return count
def get_sum (self, x, y):
return self.get_single_sum(x) + self.get_single_sum(y)
def movingCount(self, threshold, rows, cols):
"""
:type threshold: int
:type rows: int
:type cols: int
:rtype: int
"""
from collections import deque
if rows <= 0 or cols <= 0: return 0
visit = set()
queue = deque([(0, 0)])
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
result = 0
while queue:
t = queue.popleft()
s = self.get_sum(t[0], t[1])
if s > threshold or t in visit:
continue
result += 1
visit.add(t)
for i in range(4):
x = t[0] + dx[i]
y = t[1] + dy[i]
if x >= 0 and x < rows and y >= 0 and y < cols:
queue.append((x,y))
return result