地上有一个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

遍历法：很难求解，容易出错

用最笨的遍历的方法做了半个小时也没做出来，先把我的弱智垃圾还有错的代码贴在这，明天更新

class Solution: def movingCount(self, m: int, n: int, k: int) -> int: # 方法1 全部遍历 num = 0 col_flag = 0 for i in range(m): i_bitSum = int(i/10)+(i) print(i_bitSum) if k >= i_bitSum: # 行的位和不大于k for j in range(n): j_bitSum = int(j/10)+(j) print(j_bitSum) if k >= (i_bitSum + j_bitSum): num = num + 1 else: # 出现某一行的某一列中断，则后面的列也必然不连通，直接break，执行下一行 if i == 0: col_flag = j elif j >= col_flag: # 第一行的列决定了最远的位置 break else: # 若只是行的位和都比k大，则直接下一次循环即可 break # 出现一行一个都没有，则 这个图不连通，即后面的都是错误的。直接break返回 return num

因为涉及到连通图(从原点出发，一次只能上下左右移动)的问题，因此即便使用遍历，判断每一个点是否可达也是很麻烦的事情。所以还是应该用路径搜索的方法。

和上一题矩阵路径搜索类似，下面使用深度优先搜索进行求解。

深度优先搜素 DFS

思路

首先将所有点的状态记为False；

从初始点(i=0,j=0)出发，下一个目标点包括(i+1),(i-1)和(j-1),(j+1)。一旦该点不满足条件，则返回0。否则，若满足条件，则将该点记为True，表示已访问过且符合条件。

其中，条件包括：

不超过边界；位数和不大于k；未访问过。

代码

class Solution: def movingCount(self, m: int, n: int, k: int) -> int: points = [[0 for i in range(n)] for j in range(m)] # 初始点，0表示未被访问过 # 这里n是列数，m是行数！ return self.dfs(0,0,m,n,k,points) def dfs(self,i,j,m,n,k,points): # 判断是否符合条件，不符合的返回0 if (i >=m) or (i<0) or (j >=n) or (j<0) or ((self.bitSum(i)+self.bitSum(j))>k) or (points[i][j]==1): return 0 # 符合的则首先置1，再递归DFS points[i][j] = 1 return self.dfs(i+1,j,m,n,k,points) + self.dfs(i-1,j,m,n,k,points) + self.dfs(i,j+1,m,n,k,points) + self.dfs(i,j-1,m,n,k, points) +1 def bitSum(self, n): return int(n/10) + (n % 10)

 

 

Note

Python创建初始二维list的方法为

>>> a = [[0 for i in range(3)]for j in range(4)] >>> a [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]

其中，[[0 for i in range(3)]for j in range(4)] 3是列数，4是行数！因此代码里对应的是

points = [[0 for i in range(n)] for j in range(m)]