Finden Sie die Anzahl der Pfadmuster, die ein Reinigungsroboter, der sich vor und zurück sowie nach links und rechts bewegt, in 12 Schritten bewegen kann. Derselbe Ort wird jedoch nicht zweimal besucht.
Code Tiefenprioritätssuche. Schreiben Sie mit rekursiv.
N = 12 #Anzahl der Bewegungen
def dfs(path):
if len(path) > N:
return 1
cnt = 0 #Anzahl der Muster
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)])) #Ausgangsposition(0, 0)Zu
ToDo Python rekursiv scheint langsam zu sein. Ist es schneller, mit einem Stapel zu schreiben?
Recommended Posts