Source : TOI 2003

Une population de virus évolue dans un lieu assimilé à un tableau carré nxn. Un virus occupe une seule case et une case contient au plus un virus. Deux cases sont dites voisines si elles ont un sommet ou un côté communs. Deux virus sont dits voisins s'ils occupent deux cellules voisines. On appelle génération toute répartition d'un nombre de virus dans ce tableau. L'évolution d'une génération à une autre se fait selon les règles suivantes :

1 – un virus qui a au plus deux voisins (inférieur ou égal à 2), meurt de solitude.

2 – un virus qui a au moins 5 voisins (supérieur ou égal à 5), meurt asphyxié.

3 – une cellule vide ayant exactement trois cellules voisines occupées par des virus donne naissance à un nouveau virus.

On se propose d'écrire un programme qui saisit un entier n (5<n<20). Cet entier sera le côté du tableau carré où va évoluer la population des virus. Ensuite, il saisit une génération initiale de la population de ces virus. Cette entrée est composée d'une suite de couples (i, j) où 1£i£n et 1£j£n  représentant les coordonnées des cellules qui vont contenir des virus.

Le programme demande ensuite l'ordre m (1<m) de la génération qu'on voudra trouver en partant de la génération initiale.

On pourra envisager la saisie à partir d'un fichier de données (GEN_INIT.TXT)  organisé ainsi :

·        1^ère ligne contient n.

·        2^ème ligne contient m.

·        une suite de lignes comportant chacune un couple d'entiers séparés par un espace. Chaque couple d'entiers représente les deux coordonnées de la cellule où il y aura un virus.

La génération cherchée sera affichée à l'écran sous forme d'un tableau où un virus est représenté par une étoile.