Partie 3 : algorithmique

3.1. La procédure remplir.

* On a pu constater la symétrie des procédures A_droite et A_Gauche, comme par ailleurs celle de Au_Dessus et En_dessous. Les deux premières procédures, à partir d'un carré dont les coordonnéesviennent d'être dépilées, remplissent la grille à gauche et à droite, autant qu'il est possible dans les limites de carrés grisés et repèrent les bornes atteintes ; les deux dernières procédures, entre ces limites, scrutent la ligne au-dessus et la ligne au-dessous, repèrent les carrés qui pourront servir de départ de façon exclusive (deux départs sont séparés par un carré déjà occulté) et les empilent. L'itération du dépilage et de l'exécution des quatre procédures permet de remplir complètement l'îlot qui contient le carré de départ. La procédure Remplir scrute la grille, et chaque fois qu'elle trouve un carré de fond, le définit comme carré de départ (ligne 97) et remplit l'îlot (lignes 100-106). La procédure Remplir permet donc de colorer tous les carrés de fond sur la grille.

* L'appel de la procédure Tache remplit immédiatement l'îlot définit par le carré blanc de départ. On peut en conclure que si le mode utilisé pour balayer toute la grille n'est pas le plus économique, par contre, chaque appel de la procédure Tache ne peut se faire que sur des îlots différents : il suffit donc de numéroter les appels de Tache (ligne 118) pour obtenir le nombre d'îlots.

* On ne peut colorer que les carrés du fond (et une seule fois) : si c'est le carré de départ, cela est garanti par l'instruction de la ligne 047 ; et pour les autres, par le contrôle de boucle (lignes 035 et 048). Cela implique un résultats qui pourra être exploité dans la question sur les pentaminos : en comptant le nombre d'exécution des lignes 036 et 049 à l'aide d'un compteur initialisé à l'appel de Tache, on a le nombre de carrés de l'îlot.

3.2. La procédure Tache.

On trouvera ci-dessous non seulement les empilages, mais aussi l'ordre des colorations ; on pourra dérouler facilement l'appel de la procédure.

3.3. Sans cadre.

La suppression du cadre revient à décaler d'une unité les valeurs xmin, xmax,ymin, ymax . Ce changment dans la définition du tableau ne pose pas de problème en ce qui concerne l'axe vertical : les lignes 061 et 081 montrent qu'on n'utilisait pas le grisé du haut et du bas.

Pour la partie horizontale, c'est plus délicat. Il faut modifier les lignes 035 et 048 : on pourrait penser qu'un booléen supplémentaire suffirait :

Tant que ((Grille[x_local,y_depart]=fond) et (x_local>=xmin)) Faire

Mais on risque alors d'évaluer Grille[x_local,y_depart] en dehors des limites du tableau qui représente la grille, ce qui est interdit. On peut s'en sortir par exemple en employant un drapeau booléen (solution efficace qui peut déplaire aux puristes) :

Drapeau ß(x_local>=xmin)
Si Drapeau Alors
  Drapeau ß (Grille[x_local,y_depart]=fond)
Fin_de_Si_Alors

(note : on demandait de signaler la difficulté, pas de suggérer les modifications)