graph-labyrinthe.py

labyrinthe = [[0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
              [0, 1, 0, 1, 1, 1, 1, 1, 1, 0],
              [0, 1, 0, 1, 0, 0, 0, 0, 1, 0],
              [0, 1, 0, 1, 0, 1, 1, 0, 1, 0],
              [0, 0, 0, 1, 0, 1, 1, 0, 1, 0],
              [0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
              [0, 1, 0, 1, 1, 1, 1, 0, 1, 0],
              [0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
              [0, 1, 1, 1, 0, 1, 1, 1, 1, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

def affiche_labyrinthe (l):
    print('\n'.join(''.join('#' if item else '.' for item in row) for row in l))
    print()

def voisins(l, x, y):
    return ((x+dx, y+dy)
        for dx, dy in ((-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1))
        if 0 <= x+dx < len(l[0]) and 0 <= y+dy < len(l) and l[y+dy][x+dx] == 0)

# IMPORTANT : chaque appel récursif ne doit pas modifier les chemins des autres,
# donc chacun a une copie non modifiable du chemin, ce pourquoi on utilise un tuple plutôt que liste
def existe_profondeur(l, x0=0, y0=0, chemin=()):
    # print(x0, y0)
    if (x0, y0) == (len(l[0])-1, len(l)-1): # condition de terminaison
        return True
    chemin += ((x0, y0),) # on crée un nouveau chemin avec la position courante
    for x, y in voisins(l, x0, y0):
        if (x, y) in chemin: # on ignore le voisin si déjà visité par le chemin courant
            continue
        if existe_profondeur(l, x, y, chemin): # appel récursif à partir de la position voisine
            return True # on a trouvé un chemin par la position voisine, donc aussi par l'actuelle
    return False # aucun des voisins ne mène à la sortie, donc l'actuelle non plus

affiche_labyrinthe(labyrinthe)
print(existe_profondeur(labyrinthe))