Livre_silo 30 août 2013 16:32 Page 313
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
313
12 – Structure de pile
PROGRAMME 15 Construction d’un labyrinthe parfait
n = 50
atteinte = [[False] * n for i in range(n)]
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]
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
def tirage(L):
n = len(L)
assert n > 0
return L[random.randint(0, n-1)]
def labyrinthe():
pile = creer_pile(n*n)
empiler(pile, (0,0))
visiter((0,0))
while not est_vide(pile):
cellule = depiler(pile)
print(cellule)
c = choix(cellule)
if len(c) > 0:
suivante = tirage(c)
# c'est ici qu'on relie les cases cellule et suivante
visiter(suivante)
empiler(pile, cellule)
empiler(pile, suivante)