Trouvez le nombre de modèles de chemin qu'un robot de nettoyage qui se déplace d'avant en arrière et de gauche à droite peut se déplacer en 12 étapes. Cependant, le même endroit ne sera pas visité deux fois.
Code Recherche de priorité de profondeur. Écrivez en utilisant récursif.
N = 12 #Nombre de mouvements
def dfs(path):
if len(path) > N:
return 1
cnt = 0 #Nombre de motifs
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)])) #Position initiale(0, 0)À
ToDo Python récursif semble être lent. Est-il plus rapide d'écrire à l'aide d'une pile?
Recommended Posts