Fourmis et Fourmilière

Une colonie de fourmis rouges a construit sa fourmilière sous terre, dans un vaste champ. Cette colonie de fourmis est composée de F fourmis avec F étant un nombre entier. Une fourmilière est un assemblage de différentes salles, reliées les une aux autres par des tunnels. L’une de ces salles, la plus vaste, est notée Sv et correspond au vestibule de la fourmilière. L’une de ces salles, très vaste aussi, est notée Sd et correspond au dortoir, tout au fond de la fourmilière. Les autres salles de la fourmilière sont notées S1, S2, S3, .... SN. Une salle notée SN { X } est une salle pouvant accueillir X fourmis simultanément.

A la tombée de la nuit, tous les fourmis se retrouvent dans le vestibule de la fourmilière, se racontent leur journée, et se préparent à rejoindre le dortoir pour se reposer. Le vestibule, étant prêt de la surface, n’est pas un endroit très sûr. L’ensemble des fourmis doit donc rejoindre le dortoir le plus rapidement possible... Cependant ...

• Les fourmis se déplacent toutes à la même vitesse.
• Les salles de la fourmilière ne peuvent accueillir qu’une seule fourmi à la fois (en dehors du vestibule et du dortoir) sauf si spécifié autrement.
• Une fourmi ne peut s’engager dans un tunnel que si la salle de destination est vide (en dehors du dortoir) ou si la fourmi qui l’occupe est en train de partir.
• Les tunnels sont traversés instantanément par les fourmis (c’est plutôt des portes, en fait ...) L'intégralité des fourmis doivent rejoindre le dortoir en un minimum d'étapes. Lors d’une étape, chaque fourmis peut:
• Attendre dans la salle ou elle se trouve
• Se déplacer dans une salle adjacente

Pour chaque fourmilière proposée vous aurez à charge de :

• représenter la fourmilière sous forme de graphe en utilisant la librairie / module de votre choix
• afficher l’ensemble des étapes nécessaires au déplacement des fourmis, comme montré dans l’exemple ci-dessus.
• afficher graphiquement le déplacement des fourmis au sein de la fourmilière, étape par étape.