我要评论题目描述：
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
解题方法：
这个题目可以有两种解法：（1）回溯法（2）规律法（自创的）
我们首先来看回溯法~
1.回溯法
回溯法就是，我现在处于一个满足条件的格子，然后我会判断我的上下左右四个方向的格子是否满足条件，如果有1个以上的格子满足条件，那么我们可以先选一个格子，（每到一个满足条件的格子，相应的count加一），让现在的格子位置进入下一个位置，然后重复判断。当某个格子四个方向都不满足条件，或者四个方向的格子都已经走完了，这时count就已经达到最大了。
看看完整代码：
class Solution:
def Judge(self, threshold, i, j):
#判断格子位数是否满足条件
if sum(list(map(int, str(i)+str(j)))) <= threshold:
return True
else:
return False
def FindGrid(self, threshold, rows, cols, matrix, i,j):
count = 0
if i>=0 and j>=0 and i< rows and j<cols and self.Judge(threshold, i, j) and matrix[i][j]==0:
matrix[i][j]=1
count = 1+self.FindGrid(threshold, rows, cols, matrix, i, j+1)\
+self.FindGrid(threshold, rows, cols, matrix, i, j-1)\
+self.FindGrid(threshold, rows, cols, matrix, i+1, j)\
+self.FindGrid(threshold, rows, cols, matrix, i-1, j)
return count
def movingCount(self, threshold, rows, cols):
matrix = [[0 for i in range(cols)] for j in range(rows)]
count = self.FindGrid(threshold, rows, cols, matrix, 0, 0)
return count
2.规律法（想法来源于小果）
（1）寻找条件满足与条件不满足的边界：
当threshold<=9时，边界t=threshold+1,那么边界t右上方的格子均不满足。
当threshold>9时，边界t = 10*(threshold-8)+9（<=threshold+1=x/10+9）, 同样边界t上方的格子也均不满足条件，可以不遍历。
代码如下：
class Solution:
def movingCount(self, threshold, rows, cols):
if threshold<=9:
t = threshold+1
else:
t = 10*(threshold-8)+9
count = 0
for i range(rows):
for j in range(cols):
w = self.getSum(i)+self.getSum(j)
if w <= threshold and (i+j) < t :
count += 1
return count
def getSum(self,num):
while num !=0:
return num
return num%10+self.getSum(num/10)两种方法均能通过测试，其中第一种方法运行时间22ms, 第二种方法运行时间17ms。另外可以看出，第一种方法的空间复杂度为O（mn），而第二种方法为O(1)。但是规律法并不常见，也不适用。虽然在时间和空间上复杂度均比较低，但是还是推荐回溯法，毕竟这才是容易想到的编程算法啊。
本文地址：https://blog.csdn.net/peppermint_xiao/article/details/107889766
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论