Find the number of path patterns that the cleaning robot that moves back and forth and left and right can move in 12 steps. However, the same place will not be visited twice.
Code Depth-first search. Write using recursion.
N = 12 #Number of movements
def dfs(path):
if len(path) > N:
return 1
cnt = 0 #Number of patterns
for d in [(0,1), (0,-1), (1,0), (-1,0)]:
next = path[-1][0] + d[0], path[-1][1] + d[1]
if next not in path:
cnt += dfs(path + [next])
return cnt
print(dfs([(0, 0)])) #Initial position(0, 0)To
ToDo Python recursion seems to be slow. Is it faster to write using the stack?
Recommended Posts