难度: Medium
家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。
整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。
请返回整理师 总共需要整理多少个格子。
示例 1：
输入：m = 4, n = 7, cnt = 5 输出：18
提示：
1 <= n, m <= 1000 <= cnt <= 20运行时间: 76 ms
内存: 15.5 MB
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
visited = set()
def dfs(i, j):
s = sum(int(x) for x in str(i) + str(j))
if not 0 <= i < m or not 0 <= j < n or s > k or (i, j) in visited:
return 0
visited.add((i, j))
return 1 + dfs(i+1, j) + dfs(i, j+1)
return dfs(0, 0)
本题解采用深度优先搜索（DFS）的方法。从矩阵的左上角开始，递归地向右和向下进行搜索，同时跟踪已访问的节点以避免重复计算。搜索过程中，首先判断当前位置是否有效（即坐标在矩阵内，且各数位之和不超过给定的阈值k，且未被访问过），如果有效，则递归地探索当前位置的右侧和下方位置。每访问一个有效格子，就计算当前格子和其递归得到的格子数之和，最终返回总的可访问格子数。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
visited = set() # 用来存储已访问的格子
def dfs(i, j):
# 计算i和j的数位之和
s = sum(int(x) for x in str(i) + str(j))
# 判断位置是否有效
if not 0 <= i < m or not 0 <= j < n or s > k or (i, j) in visited:
return 0
visited.add((i, j)) # 标记当前格子为已访问
# 递归地访问下一个格子，并累加可访问的格子数
return 1 + dfs(i+1, j) + dfs(i, j+1)
return dfs(0, 0) # 从左上角开始搜索
在解决路径搜索问题时，深度优先搜索(DFS)和广度优先搜索(BFS)各有优势。对于本题，DFS的优势在于实现简单，易于递归调用。DFS可以直接利用递归堆栈跟踪路径，而BFS则需要显式使用队列来存储未探索的节点。此外，DFS在遇到无效节点时可以立即回溯，这有助于减少不必要的计算和空间占用。虽然BFS也可以工作，但在这种情况下，DFS的空间和时间效率稍优，特别是在矩阵较大且阈值k较小导致可访问区域较小的情况下。
为了防止递归过深导致栈溢出，通常需要对递归的深度进行控制。在本题中，递归的最大深度受到矩阵的大小和阈值k的限制。由于每次递归都需要满足数位和的条件，这通常限制了递归的深度。例如，当矩阵的尺寸很大但k非常小时，许多路径都会因为数位和过大而被剪枝，从而减少递归深度。此外，递归中还加入了检查是否已访问的逻辑，进一步减少不必要的递归调用。如果实际应用中仍担心栈溢出，可以考虑使用迭代的DFS实现，利用显式栈来模拟递归。
在计算数位之和时，当前实现通过转换数字为字符串然后再进行迭代求和是有效的，但存在一定的性能开销。一个更高效的方法是直接使用数学计算：通过对数字连续使用除法和取模操作来提取每一位。例如，可以定义一个辅助函数，使用循环来提取每一位并累加。这种方法避免了字符串操作的开销，对于大数字或大矩阵更为高效。