Livre_silo 30 août 2013 16:32 Page 311
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
311
12 – Structure de pile
Il faut également une matrice (n, n) de booléens indiquant, pour chaque case, si elle a déjà
été atteinte par un chemin (initialement False) :
atteinte = [[False] * n for i in range(n)]
On se donne deux fonctions visiter et est_atteinte pour respectivement modifier et consulter le contenu de la matrice atteinte :
def visiter(c):
(x,y) = c
if x < 0 or x >= n or y < 0 or y >= n:
return
atteinte[x][y] = True
def est_atteinte(c):
(x,y) = c
if x < 0 or x >= n or y < 0 or y >= n:
return True
return atteinte[x][y]
La première fonction prend soin de ne pas écrire à l’extérieur de la matrice et la seconde
considère les cases extérieures au labyrinthe comme déjà atteintes. Dans les deux fonctions,
on commence par déconstruire l’argument c qui est un couple.
On écrit maintenant une fonction choix qui, étant donnée une position (x,y), détermine les
positions adjacentes non encore visitées. Le résultat est renvoyé sous la forme d’un tableau
(contenant donc de 0 à 4 éléments) :
def choix(c):
(x,y) = c
r = []
def ajouter(p):
if not est_atteinte(p): r.append(p)
ajouter((x-1, y))
ajouter((x+1, y))
ajouter((x, y-1))
ajouter((x, y+1))
return r
Le tableau résultat r est rempli par la fonction locale ajouter. Ainsi, on factorise l’appel
à est_atteinte. On note qu’on utilise ici la méthode append, exactement comme on l’a fait
pour écrire la fonction empiler.
L’étape suivante consiste en une fonction qui prend un élément au hasard dans un tableau.
Elle servira à choisir aléatoirement parmi les directions possibles renvoyées par la fonction
choix précédente :
def tirage(L):
n = len(L)
assert n > 0
return L[random.randint(0, n-1)]
Cette fonction suppose que le tableau n’est pas vide (d’où le assert) et utilise la fonction de
bibliothèque random.randint pour choisir un élément.