剑指 Offer 13. 机器人的运动范围
剑指 Offer 13. 机器人的运动范围

⁠

剑指 Offer 13. 机器人的运动范围⁠

⁠

BFS:

# 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))

# path = set()

# while not q.empty():

# x, y = q.get_nowait()

# if (x, y) not in path and 0 <= x < m and 0 <= y < n and digitSum(x) + digitSum(y) <= k:

# path.add((x, y))

# for nx, ny in [(x + 1, y), (x, y + 1)]:

# q.put((nx, ny))

# return len(path)

DFS:

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:

def dfs(i, j):

if i >= m or j >= n or k < digitSum(i) + digitSum(j) or (i, j) in visited: return 0

visited.add((i, j))

return 1 + dfs(i, j + 1) + dfs(i + 1, j)

visited = set()

return dfs(0, 0)

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.

剑指 Offer 13. 机器人的运动范围剑指 Offer 13. 机器人的运动范围