Propagation
Objectif : sélectionner les cases d’un tableau possédant les mêmes caractéristiques par propagation à partir une case.
Ce type d’algorithme est par exemple utilisé au sein du jeu de démineur, ou bien par les logiciel de dessin pour l’outil « baguette magique ».
Pour cet exercice, on représentera la grille par un tableau (liste de listes en Python) contenant des entiers.
Une case « sélectionnée » aura pour valeur -1, et sera représentée par le caractère "█" (full block) et pour plus de visibilité, une case de valeur nulle sera représentée par le caractère " " (espace). Toutes les autres cases auront pour valeur un entier à un seul chiffre.
Écrire une fonction
construire_grille qui prend en argument les dimensions w (largeur) et h (hauteur) et renvoie un tableau (une liste de listes) dont toutes les cases contiennent la valeur 0 par défaut.
Écrire une fonction
peupler_grille, qui prend en argument un tableau (créé avec construire_grille) et un entier v donnant la valeur à placer dans la grille (v peut signifier le code ascii d’un caractère par exemple) et un entier n désignant le nombre d’occurrences de ce nombre à placer dans la grille. Les n entiers v sont placés aléatoirement dans la grille.
Écrire une fonction
afficher_grille, qui prend en argument un tableau (créé avec construire_grille et peuplé avec peupler_grille), qui affiche le tableau dans la console de sorte que lignes et colonnes soient correctement alignées et réparties.
Écrire une fonction (récursive !)
La propagation se fait exclusivement par les cotés adjacents à la case (gauche, droite, haut et bas), et non par les diagonales.
propager, qui prend en argument un tableau g (une « grille ») et un tuple depart désignant une de ses cases (au format (ligne, colonne)).La propagation se fait exclusivement par les cotés adjacents à la case (gauche, droite, haut et bas), et non par les diagonales.
On constate qu’à plusieurs reprises dans le programme, il faut déterminer les dimensions de la grille passée en argument aux fonctions. Afin d’éviter cela, il serait préférable de mémoriser ces valeurs (qui ne changent jamais), au sein même de la grille. Pour cela, rien de tel que la Programmation Orientée Objet.
Modifier ce programme en transformant les fonctions en méthodes d’une classe
Grille.
