本文共 4348 字，大约阅读时间需要 14 分钟。

【题目描述】

地上有一个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.数位之和计算

设一数字 x ，向下取整除法符号 // ，求余符号 ⊙ ，则有：

• x⊙10 ：得到 x 的个位数字；
• x // 10 ： 令 x 的十进制数向右移动一位，即删除个位数字。

因此，可通过循环求得数位和 s ，数位和计算的封装函数如下所示（将每个个位数累加）：

def sums(x):    s = 0    while x != 0:        s += x % 10        x = x // 10    return s

由于机器人每次只能移动一格（即只能从 x 运动至 x±1），因此每次只需计算 x 到 x±1 的数位和增量。本题说明 1≤n,m≤100 ，以下公式仅在此范围适用。

故：以下代码为增量公式的三元表达式写法，

s_x+1 if (x+1)%10 else s_x-8

2.可达解分析

根据数位和增量公式得知，数位和 每逢 进位 突变一次。根据此特点，矩阵中 满足数位和的解 构成的几何形状形如多个 等腰直角三角形 ，每个三角形的直角顶点位于 0, 10, 20, … 等数位和突变的矩阵索引处 。

.

三角形内的解虽然都满足数位和要求，但由于机器人每步只能走一个单元格，而三角形间不一定是连通的，因此机器人不一定能到达，称之为 不可达解 ；同理，可到达的解称为 可达解 （本题求此解） 。

图例展示了 n = m = 20, k∈[6,19] 的可达解、不可达解、非解，以及连通性的变化。

【法一】深度优先遍历 DFS

class Solution:    def movingCount(self, m: int, n: int, k: int) -> int:        def dfs(i, j, si, sj):        	# 终止条件            if i >= m or j >= n or k < si + sj or (i, j) in visited:             	return 0                        # 递推工作            # 1.标记当前单元格            visited.add((i,j))            # 2.搜索下一单元格            # xia_da = dfs(i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj)        	#you_da = dfs(i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8)        	# total = 1 + xia_da + you_da        	# print('下达：',xia_da,'\t','右达：',you_da,end='\t')        	# print('total =',total)			return 1 + dfs(i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj) + dfs(i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8)        visited = set()        return dfs(0, 0, 0, 0)'''作者：jyd链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/'''

【打印版 m=3, n=4, k=2】visited =  {
   (0, 0)}visited =  {
   (1, 0), (0, 0)}visited =  {
   (1, 0), (2, 0), (0, 0)}下达： 0         右达： 0       total = 1visited =  {
   (1, 0), (1, 1), (2, 0), (0, 0)}下达： 0         右达： 0       total = 1下达： 1         右达： 1       total = 3visited =  {
   (0, 1), (0, 0), (1, 1), (2, 0), (1, 0)}visited =  {
   (0, 1), (0, 0), (1, 1), (2, 0), (0, 2), (1, 0)}下达： 0         右达： 0       total = 1下达： 0         右达： 1       total = 2下达： 3         右达： 2       total = 6

复杂度分析：

设矩阵行列数分别为 M, N 。

• 时间复杂度 O(MN) ： 最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为 O(MN) 。
• 空间复杂度 O(MN)： 最差情况下，Set visited 内存储矩阵所有单元格的索引，使用 O(MN) 的额外空间。

【法二】广度优先遍历 BFS

class Solution:    def movingCount(self, m: int, n: int, k: int) -> int:	     # 初始化	    queue, visited = [(0, 0, 0, 0)], set()	    while queue:    # 终止条件： queue 为空	        # 1.单元格出队	        i, j, si, sj = queue.pop(0)	        # 2.判断是否跳过	        if i >= m or j >= n or k < si + sj or (i, j) in visited: 	            continue	        	        # 3.标记当前单元格	        visited.add((i,j))	        # print('visited = ',visited)	        # 4.单元格入队	        queue.append((i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj))	        queue.append((i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8))	        # print('出队后,当前queue:',queue)        return len(visited)'''作者：jyd链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/'''

visited =  {
   (0, 0)}出队后,当前queue: [(1, 0, 1, 0), (0, 1, 0, 1)]visited =  {
   (1, 0), (0, 0)}出队后,当前queue: [(0, 1, 0, 1), (2, 0, 2, 0), (1, 1, 1, 1)]visited =  {
   (1, 0), (0, 1), (0, 0)}出队后,当前queue: [(2, 0, 2, 0), (1, 1, 1, 1), (1, 1, 1, 1), (0, 2, 0, 2)]visited =  {
   (1, 0), (0, 1), (2, 0), (0, 0)}出队后,当前queue: [(1, 1, 1, 1), (1, 1, 1, 1), (0, 2, 0, 2), (3, 0, 3, 0), (2, 1, 2, 1)]visited =  {
   (0, 1), (0, 0), (1, 1), (2, 0), (1, 0)}出队后,当前queue: [(1, 1, 1, 1), (0, 2, 0, 2), (3, 0, 3, 0), (2, 1, 2, 1), (2, 1, 2, 1), (1, 2, 1, 2)]visited =  {
   (0, 1), (0, 0), (1, 1), (2, 0), (0, 2), (1, 0)}出队后,当前queue: [(3, 0, 3, 0), (2, 1, 2, 1), (2, 1, 2, 1), (1, 2, 1, 2), (1, 2, 1, 2), (0, 3, 0, 3)]6

复杂度分析：

设矩阵行列数分别为 M, N。

• 时间复杂度 O(MN) ： 最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为 O(MN) 。
• 空间复杂度 O(MN)： 最差情况下，Set visited 内存储矩阵所有单元格的索引，使用 O(MN) 的额外空间。

​

转载地址：http://qfjii.baihongyu.com/