©2020-2024 ioDraw All rights reserved,
Privacy Policy
DFS即Depth First Search，是一种用于遍历或搜索树或图的算法。
沿着树的深度遍历树的节点，尽可能深的搜索树的分支。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
##DFS模块基本步骤 DFS(dep,...) { if (找到解 or 走不下去了) { ... return } 枚举下一种可能出现的情况，DFS(
dep+1,...) }
<>例题
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。
例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 =
19。请问该机器人能够达到多少个格子？
思路：利用回溯法遍历所有元素，记录满足条件的路径，为了简单起见，我们可以只从两个方向寻找，向右与向下。需要注意的是边界条件。
class Solution3: def movingCount(self, threshold, rows, cols): # 计算每一位之和 def
getsum(num): sum = 0 while num>0: sum += num%10 num = num//10 return sum path =
[] def back(start): if start in path or getsum(start[0]) + getsum(start[1])>
threshold: return None if start[0]>=rows or start[1]>=cols: return None path.
append(start) # 从0，0开始向右向下遍历，减少走回头路的次数 print(path) back([start[0]+1,start[1]])
back([start[0],start[1]+1]) """ if start[0]>=rows or start[1]>=cols or
start[0]<0 or start[1]<0: return None path.append(start) #
从0，0开始向右向下遍历，减少走回头路的次数 back([start[0]+1,start[1]]) back([start[0]-1,start[1]])
back([start[0],start[1]-1]) back([start[0],start[1]+1]) """ back([0,0]) return
len(path) print(Solution3().movingCount(4,3,5))
方法二
与方法一种保存每一条符合条件的路径不同，该方法是通过构建一个同等大小的矩阵，记录走过的路径，然后在四个方向深度搜索。
class Solution2: def __init__(self): self.count = 0 def movingCount(self,
threshold, rows, cols): # write code here arr = [[1 for i in range(cols)] for j
in range(rows)] self.findway(arr, 0, 0, threshold) return self.count def findway
(self, arr, i, j, k): if i < 0 or j < 0 or i >= len(arr) or j >= len(arr[0]):
return tmpi = list(map(int, list(str(i)))) # 将一个整型数字转化字符串类型，然后在列表化，最后在转化为整型。
12——[1,2] tmpj = list(map(int, list(str(j)))) if sum(tmpi) + sum(tmpj) > k or
arr[i][j] != 1: return arr[i][j] = 0 #记录走过的路径 self.count += 1 self.findway(arr,
i+ 1, j, k) self.findway(arr, i - 1, j, k) self.findway(arr, i, j + 1, k) self.
findway(arr, i, j - 1, k)
方法三
1、从(0,0)开始走，每成功走一步标记当前位置为true,然后从当前位置往四个方向探索，
返回1 + 4 个方向的探索值之和。
2、探索时，判断当前节点是否可达的标准为：
1）当前节点在矩阵内；
2）当前节点未被访问过；
3）当前节点满足limit限制。
class Solution: def movingCount(self, threshold, rows, cols): # write code here
if not threshold or not rows or not cols: return 0 # 定义每格标志位： 0代表没走过； 1代表走过
visited= [0]*(rows * cols) for row in range(rows): for col in range(cols):
return self.movingCountCore(threshold, rows, cols, row, col, visited) # 数字数位求和函数
def digitSum(self, dig): re = 0 while dig: re = re + dig % 10 dig = dig // 10
return re # 递归回溯判断每步是否可行，并返回计数和累加 def movingCountCore(self, threshold, rows,
cols, row, col, visited): count = 0 if 0 <= row < rows and 0 <= col < cols\ and
self.digitSum(row) + self.digitSum(col) <= threshold and visited[row * cols +
col] == 0: visited[row * cols + col] = 1 print("visited:",visited) #
在递归中，依次遍历每个元素的上下左右四个元素，如果满足条件，则继续递归，递归过的每一个元素都进行标记 count = 1 + self.
movingCountCore(threshold, rows, cols, row - 1, col, visited) \ + self.
movingCountCore(threshold, rows, cols, row + 1, col, visited) \ + self.
movingCountCore(threshold, rows, cols, row, col - 1, visited) \ + self.
movingCountCore(threshold, rows, cols, row, col + 1, visited) print("count:",
count) return count # print(Solution().movingCount(10,7,7))
<>总结
类似的求路径都可以用这种无脑深度优先搜索法去解决，即回溯的思想，需要注意的是递归的终止条件。