- 标签:深度优先搜索、广度优先搜索、动态规划
- 难度:中等
题目大意
#
有一个 m * n
大小的方格,坐标从 (0, 0)
到 (m - 1, n - 1)
。一个机器人从 (0, 0)
处的格子开始移动,每次可以向上、下、左、右移动一格(不能移动到方格外),也不能移动到行坐标和列坐标的数位之和大于 k
的格子。现在给定 3
个整数 m
、n
、k
。
要求:计算并输出该机器人能够达到多少个格子。
解题思路
#
使用广度优先搜索解决问题。
先定义一个计算数位和的方法 digitsum
。然后通过队列进行广度优先搜索。
- 将
(0, 0)
加入队列,当队列不为空时,每次将队首坐标弹出,加入访问集合 visited
中。
- 再将满足行列坐标的数位和不大于
k
的格子坐标加入到队列中,继续弹出队首坐标。
- 直到队列为空时停止。输出访问集合的长度。
代码
#
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
|
import collections
class Solution:
def digitsum(self, n: int):
ans = 0
while n:
ans += n % 10
n //= 10
return ans
def movingCount(self, m: int, n: int, k: int) -> int:
queue = collections.deque()
queue.append((0, 0))
visited = set()
while queue:
x, y = queue.popleft()
if (x, y) not in visited and self.digitsum(x) + self.digitsum(y) <= k:
visited.add((x, y))
for dx, dy in [(1, 0), (0, 1)]:
nx = x + dx
ny = y + dy
if 0 <= nx < m and 0 <= ny < n:
queue.append((nx, ny))
return len(visited)
|