一、题目
地上有一个m行n列的方格，从坐标[0,0]到坐标[m-1,n-1]。一个机器人从坐标[0, 0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例1：
输入：m = 2, n = 3, k = 1
输出：3示例2：
输入：m = 3, n = 1, k = 0
输出：1提示：
1 <= n,m <= 1000 <= k <= 20
二、思路
详细题解请参见Leetcode官方题解
1. 深度优先搜索
这一题机器人要从坐标[0,0]到坐标[m-1, n-1]也就是要从左上角到达右下角。这个机器人可以向左、右、上、下四个方向移动，所以我们可以将初始坐标传入递归函数，然后执行四个方向的递归操作，匹配出所有的可达到格子。
在进行操作之前呢，我们必须对坐标进行判断是否在方格范围内，也就是题目中所要求的1 <= n,m <= 100，所以行和列的范围0 <= i <= m-1、0 <= j <= n-1。不满足这个条件，便可以退出递归了。
当到达一个格子的时候，我们还必须进行判断这个格子是否已经访问过。如果访问过，那么就应该结束在这个方向的前进。所以，我们创建一个二维数组dp[i][j]来保存每一个格子的访问状态，初始状态全部设置为0，表示都未访问过。
如果到达的格子未访问过，那么我们就需要将行坐标和列坐标的数位之和与k值大小进行比较。大于k值，当前递归结束，否则，便可以将该格子访问状态置为1。同时，我们使用一个变量res来统计可到达格子的数量。此时将res值加1。
那么，如何计算数位之和呢？因为i和j都为两位数，所以这里选择直接使用divmod方法分别对i和j求商和余数，然后将它们的商和余数相加求和，便可得到数位之和。
在全部递归结束以后，返回res即可。
实际上在这一题中，还隐藏一个点，那就是从左上角到右下角只需要向下或者向右移动即可。
2. 广度优先搜索
这种方法与上述深度优先搜索的思路是一样的，只不过在广度优先搜索中我们使用集合来保存可到达格子的坐标，使用队列来存放接下来即将访问的坐标。最后返回集合的长度便是可到达方格的数量。
三、代码
1. 深度优先搜索
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
def recursion(i, j):
nonlocal res
if not 0 <= i <= m-1 or not 0 <= j <= n-1:
return
if dp[i][j] != 0:
return
div1, mod1 = divmod(i, 10)
div2, mod2 = divmod(j, 10)
if (div1 + mod1 + div2 + mod2) > k:
dp[i][j] = -1
return
dp[i][j] = 1
res += 1
# 左 这一步递归可注释掉，没必要执行
recursion(i, j-1)
# 右
recursion(i, j+1)
# 上 这一步可注释掉
recursion(i-1, j)
# 下
recursion(i+1, j)
# 统计格子访问状态
dp = [[0 for _ in range(n)] for _ in range(m)]
# 统计可以到达的格子数量
res = 0
recursion(0, 0)
return res2. 广度优先搜索
from queue import Queue
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
def divmods(num):
div, mod = divmod(num, 10)
return div + mod
q = Queue()
q.put((0, 0))
# 坐标集合, 去重，并且提高速度
coordinates = set()
while not q.empty():
i, j = q.get()
if 0 <= i < m and 0 <= j < n and (i, j) not in coordinates and divmods(i) + divmods(j) <= k:
coordinates.add((i, j))
q.put((i+1,j))
q.put((i,j+1))
return len(coordinates) 四、表现
| method | 运行时间 | 表现 | 内存消耗 | 表现 |
|---|---|---|---|---|
| 1. 1 深度优先搜索 | 60ms | 67.02% | 15.9MB | 16.47% |
| 1.2 改进版 | 40ms | 99.58% | 14MB | 40.09% |
| 2. 广度优先搜索 | 128ms | 14.15% | 13.8MB | 56.45% |
