TP n°10 d'informatique en DEUG S1 MIAS +MASS (2000-2001)
JEU DU DEMINEUR

1) LE JEU

    Un terrain miné est représenté par un tableau carré à deux indices. Chaque case contient 0 (pas de mine) ou 1 (présence d'une mine). Les mines sont réparties aléatoirement mais sans pouvoir se toucher.

    Le jeu consiste à déminer progressivement le terrain sans toucher aux mines. Pour cela, le joueur choisit le numéro de ligne et le numéro de colonne d'une case du terrain dont il ignore le contenu (case restant à déminer). S'il tombe sur 1 (présence d'une mine) il a perdu et le jeu s'arrête. S'il tombe sur 0 (absence de mine) la case correspondante devient déminée. Le joueur dispose alors d'un détecteur de mines qui calcule l enombre total de mines entourant la case qu'il vient de déminer. Si ce total est nul, les cases voisines ne contiennent pas de mines et deviennent ainsi déminées. Lorsque, par ce processus, une case devient entourée de cases déminées, elle devient elle aussi diminée. Dans le cas où cette dernière contient une mine, celle-ci est neutralisée. Le jeu s'arrête lorsque toutes les mines sont ainsi neutralisées.

    A chaque étape du jeu, l'état d'avancement du déminage du terrain est affiché de façon à aider le joueur : (cf exemple)

- pour une case non encore déminée il s'affiche un ?

- pour une case déjà déminée deux cas sont distinguées :

-  ou bien toutes les cases qui l'entourent sont elles aussi déminées et il s'affiche un . si elle ne contient pas de mine ou un ! si elle en contient une.

- ou bien il existe au moins une case qui l'entoure non déminée et il s'affiche le nombre de mines l'entourant calculé par le détecteur de mines.

2) PROGRAMMATION

Structures de données

On utilisera 3 tableaux à 2 indices variant de -1 à 22 :

- un tableau TERRAIN contenant des 0 et des 1 et qui représente la répartition des mines sur le terrain.

- un tableau DETECTEUR dont la composante i,j contient le nombre total de mines entourant la case i,j du terrain.

- un tableau DEMINE dont la composante i,j contient true ou false selon que la case i,j du terrain a été déminé ou pas.

    Comme dans le courant du jeu, on est amené à examiner ce qui se passe autour d'une case donnée du terrain (Y-a-t'il des mines autour ? Son déminage a-t-il neutralisé une mine ?) on peut déborder du cadre strict du jeu. C'est pourquoi on doit prévoir une marge de 2 cases tout autour des tableaux afin d'éviter tout dépassement des bornes. Cette marge correspond aux valeurs des indices -1, 0, 21 et 22.

Sous programmes

    Ecrire un sous programme TOTAL_AUTOUR qui à une case i,j d'un tableau A carré de composantes entières, associe le total des cases qui l'entourent.

    Ecrire un sous programme VRAI_AUTOUR qui, pour une case i,j d'un tableau B carré de composantes booléennes, détermine si cette case est entourée ou non de cases qui contiennent toutes true.

    Ecrire un sous programme sans parametre qui affiche l'état du déminage comme décrit ci dessous.

Programme principal

    L'utilisateur choisit la taille t du terrain à miner entre 1 et 20 puis le nombre m de mines entre 1 et t.
    Le programme remplit le tableau TERRAIN de 0 pour les indices entre -1 et t+2, puis tire au sort la position des mines entre 1 et t en s'arrangeant pour qu'elles ne se touchent pas.
    Il calcule et remplit le tableau DETECTEUR pour les indices entre 1 et t et avec true ailleurs.
    Le déminage s'effectue alors et s'arrête soit parce que le joueur est tombé sur une mine (il a perdu), soit parce qu'il a neutralisé toutes les mines (il a gagné). L'affichage du terrain entièrement déminé s'effectue alors.

EXEMPLES
              1 2 3 4 5          1 2 3 4 5
             ----------         ----------
t=5       1 | 0 0 0 0 0      1 | 1 1 1 1 1
          2 | 1 0 0 1 0      2 | 0 1 1 0 1
m=3       3 | 0 0 0 0 0      3 | 1 1 2 2 2
          4 | 0 0 0 1 0      4 | 0 0 1 0 1
          5 | 0 0 0 0 0      5 | 0 0 1 1 1

              TERRAIN           DETECTEUR
         (sans les marges)       (idem)

              1 2 3 4 5          1 2 3 4 5
             ----------         ----------
 en       1 | . . 1 ? ?      1 | T T T F F
          2 | ! . 1 ? ?      2 | T T T F F
cours     3 | . . 2 ? ?      3 | T T T F F
          4 | . . 1 ? ?      4 | T T T F F
de jeu    5 | . . 1 1 1      5 | T T T T T

             AFFICHAGE            DEMINE