NSI Terminale
def cree_graphe(laby: list[list])->dict:
"""Fonction qui crée le graphe modélisant un labyrinthe décrit par un tableau de tableaux.
Entrée:
laby = tableau de tableaux modélisant le graphe - Codage : 0 = case vide / 1 = mur
Sortie :
le graphe ( dictionnaire de listes d'adjacence ). Chaque sommet y est désigné par un tuple (ligne, colonne) dans le labyrinthe
"""
g = {} # Graphe vide pour l'instant
for i in range(len(laby)): # Pour chaque ligne du tableau,
for j in range(len(laby[0])): # Pour chaque case de la ligne,
if laby[i][j] == 0: # si la case contient la valeur 0,
g[(i, j)] = [] # on crée le sommet (i, j) ( avec aucun voisin pour l'instant );
if laby[i-1][j] == 0: # si la case AU DESSUS contient aussi 0,
g[(i, j)].append((i-1, j)) # on crée un arc de (i, j) vers (i-1, j),
g[(i-1, j)].append((i, j)) # mais aussi dans l'autre sens ( arête ) !
if laby[i][j-1] == 0: # idem pour la case A GAUCHE
g[(i, j)].append((i, j-1))
g[(i, j-1)].append((i, j))
return g
Le plus dur est fait ! Pour la détermination du parcours de sortie, on réutilisera simplement les fonctions écrites à la page précédente, à savoir la recherche de chemin entre deux sommets et la reconstruction de ce chemin.
Pour cette dernière fonction, on pourra stocker les tuples représentant les sommets à suivre dans un tableau :
def resoudre(g: dict, depart: tuple, arrivee: tuple)->list:
"""Fonction qui détermine le chemin à suivre pour sortir d'un labyrinthe.
Entrée:
g = graphe modélisant le labyrinthe
depart = tuple (ligne, colonne) représentant le sommet de départ
arrivee = idem pour le sommet d'arrivée
Sortie :
la liste des sommets à suivre pour aller du sommet de départ à celui d'arrivée
"""
pile = [] # utilisation d'une simple liste comme pile
pred = {depart: None} # dictionnaire des prédécesseurs/des sommets déjà visités
pile.append(depart)
while pile != []:
u = pile.pop()
if u == arrivee:
return chemin(arrivee, pred)
for v in g[u]:
if v not in pred:
pred[v] = u
pile.append(v)
return False
def chemin(s: tuple, pred: dict)->list:
"""Renvoi du chemin à parcourir sous forme de tableau des sommets successifs."""
if pred[s] == None :
return [s]
else:
return chemin(pred[s], pred) + [s]
resoudre(cree_graphe(laby), (0, 1), (8, 14)))
# Doit renvoyer :
# [(0, 1), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (2, 5), (1, 5), (1, 6), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (5, 8), (5, 9), (5, 10), (5, 11), (5, 12), (6, 12), (7, 12), (7, 13), (7, 14), (8, 14)]
Pour l'affichage , on parcourt le tableau de tableaux représentant le labyrinthe :
import matplotlib.pyplot as plt
def affiche(laby: list, chemin: list):
for i in range(len(laby)): # pour chaque ligne du tableau de tableaux,
for j in range(len(laby[0])): # pour chaque colonne de la ligne courante,
if (i, j) in chemin: # si la case (i, j) se trouve dans le chemin de sortie,
laby[i][j] = 2 # alors on affecte la valeur 2 à l'élément correspondant
plt.imshow(laby)
plt.show()
def extraire_donnes(fichier)->list:
"""Extrait d'un fichier .txt les données d'un labyrinthe
Entrée:
fichier = le nom du fichier .txt
Sortie :
le tableau de tableaux représentant le labyrinthe
"""
laby = []
with open(fichier, 'r') as f: # ouverture du fichier en lecture
i = 0 # numéro de la ligne
for ligne in f: # lecture du fichier ligne par ligne; la variable 'ligne' est une chaîne de caractères ( str )
row = [] # tableau représentant la ligne
ligne = ligne.rstrip('\n') # suppression du caractère de retour à la ligne en fin de ligne
for j in range(len(ligne)):
if ligne[j] =='4': # case (i, j ) = entrée ?
entree = (i, j)
row.append(0) # l'entrée est une case accessible...
elif ligne[j] =='5': # case (i, j ) = sortie ?
sortie = (i, j)
row.append(0) # idem...
else:
row.append(int(ligne[j])) # pour tout autre case ( mur ou case accessible )
laby.append(row) # addition de la ligne en fin du tableau de tableaux
i += 1 # incrémentation du compteur de ligne
return laby, entree, sortie
laby, entree, sortie = extraire_donnes("laby2.txt")
Le code complet ici.
def creer_laby(laby: list[list], s: tuple, visites: list, debuts: list)->list[list]:
"""Fonction qui crée un tableau de tableaux représentant un labyrinthe, à l'aide de l'algorithme de parcours en profondeur avec retour en arrière.
Entrées :
laby = le tableau de tableaux représentant le labyrinthe, ne contenant que des murs au premier appel
s = la case courante
visites = la liste des cases déjà explorées
débuts = la liste des débuts de chemin
Sortie:
le tableau de tableaux modifié
'''
visites.append(s)
i = s[0]
j = s[1]
voisins_courant = []
if i >= 3 and (i-2, j) not in visites:
voisins_courant.append((i-2, j))
if i <= h-4 and (i+2, j) not in visites:
voisins_courant.append((i+2, j))
if j >= 3 and (i, j-2) not in visites:
voisins_courant.append((i, j-2))
if j <= l-4 and (i, j+2) not in visites:
voisins_courant.append((i, j+2))
if voisins_courant != []:
shuffle(voisins_courant) # on mélange aléatoirement le tableau des voisins,
v = voisins_courant.pop() # et on en extrait le dernier élément.
debuts.append(s)
laby[(s[0]+v[0])//2][(s[1]+v[1])//2] = 0 # on "casse" le "mur" entre la case courante et le voisin sélectionné...
creer_laby(laby, v, visites, debuts)
elif debuts != []:
v = debuts.pop()
creer_laby(laby, v, visites, debuts)
return laby