[PYTHON] Mathematik-Puzzle zum Trainieren des Gehirns des Programmierers Q08 Ausgezeichneter Reinigungsroboter

Problemzusammenfassung

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

Mathematik-Puzzle zum Trainieren des Gehirns des Programmierers Q08 Ausgezeichneter Reinigungsroboter
Mathe-Puzzle, um das Gehirn des Programmierers zu trainieren Q05 Zahlen Sie immer noch bar?
Mathe-Puzzle zum Trainieren des Gehirns des Programmierers Q04 Schnitzen eines Stocks
Mathe-Puzzle zum Trainieren des Gehirns des Programmierers Q01 "Wiederholung in Dezimalzahl"
Mathe-Puzzle zum Trainieren des Gehirns des Programmierers Q03 Drehen Sie die Karte um
Mathematik-Puzzle zum Trainieren des Gehirns des Programmierers Q06 (modifizierte Version) Koratz 'Vorhersage