DFS Namely Depth First Search, Is an algorithm used to traverse or search trees or graphs .
Traverse the nodes of the tree along the depth of the tree , Search the branches of the tree as deep as possible . In brief, the process is to go deep into every possible branch path until it can't go any further , And each node can only be accessed once .
##DFS Basic steps of module DFS(dep,...) { if ( Find solution or I can't go on ) { ... return } Enumerate the next possible situation ,DFS(
dep+1,...) }
<> Examples
There is one on the ground m Line sum n Grid of columns . A robot from coordinates 0,0 The grid begins to move , You can only turn left at a time , right , upper , Move one grid in the next four directions , However, the sum of digits of row coordinates and column coordinates cannot be greater than k Lattice of .
for example , When k by 18 Time , The robot can enter the grid （35,37）, because 3+5+3+7 = 18. however , It cannot enter the grid （35,38）, because 3+5+3+8 =
19. How many grids can the robot reach ?
thinking ： Use backtracking to traverse all elements , Record the path that meets the conditions , For simplicity , We can look in only two directions , Right and down . Note the boundary conditions .
class Solution3: def movingCount(self, threshold, rows, cols): # Calculate the sum of each bit 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) # from 0,0 Start right down traversal , Reduce the number of turns 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) #
from 0,0 Start right down traversal , Reduce the number of turns 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))
Method 2
It is different from the method of saving each qualified path , The method is by constructing a matrix of the same size , Record the path taken , Then search in depth in four directions .
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)))) # Converts an integer number to a string type , Then list it , Finally, it is converted to integer .
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 # Record the path taken 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)
Method 3
1, from (0,0) Start walking , Mark each step as successful true, Then explore in four directions from the current position ,
return 1 + 4 Sum of exploration values in two directions .
2, When exploring , The criteria for judging whether the current node is reachable are ：
1） The current node is in the matrix ;
2） The current node has not been accessed ;
3） Current node meets limit limit .
class Solution: def movingCount(self, threshold, rows, cols): # write code here
if not threshold or not rows or not cols: return 0 # Define the flag bit of each grid ： 0 The representative didn't walk through ; 1 Representative walk
visited= [0]*(rows * cols) for row in range(rows): for col in range(cols):
return self.movingCountCore(threshold, rows, cols, row, col, visited) # Digital summation function
def digitSum(self, dig): re = 0 while dig: re = re + dig % 10 dig = dig // 10
return re # Recursive backtracking determines whether each step is feasible , And returns counting and accumulation 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) #
In recursion , Traverse the upper, lower, left and right elements of each element in turn , If the conditions are met , Then continue recursion , Each recursive element is marked 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))
<> summary
Similar path finding can be solved by this mindless depth first search method , The idea of backtracking , Note the termination condition of recursion .
Technology