#! /usr/bin/python3

from labyrinthe import *

def trouve_chemin(t):
    p = len(t)
    q = len(t[0])
    # Matrice de coordonnées disant, pour chaque pièce rencontrée, d'où
    # on venait lorsqu'on l'a rencontrée.
    origine = [[None for j in range(q)] for i in range(p)]
    pile = [(0, 0)]
    # Pour le cas particulier de la pièce d'entrée, on considère qu'on
    # arrive d'une pièce fictive (-1, 0).
    origine[0][0] = (-1, 0) 
    while pile != [] and pile[-1] != (p-1, q-1):
        (i, j) = pile.pop()
        for (i2, j2) in t[i][j]:
            if origine[i2][j2] is None:
                pile.append((i2, j2))
                origine[i2][j2] = (i, j)
    xs = []
    ys = []
    i, j = p-1, q-1
    while (i, j) != (-1, 0):
        xs.append(i)
        ys.append(j)
        i, j = origine[i][j]
    pl.plot(xs, ys, color="red")
            
t = construit_labyrinthe(20, 20)

dessine_labyrinthe(t)

trouve_chemin(t)

pl.show()