TD 7 : Tableaux à deux dimensions (tableaux 2D)

TD 7 : Tableaux à deux dimensions (tableaux 2D)#

Notes aux enseignants

Après les examens mi-semestre, il est fort possible que l’on constate une certaine démotivation, fatigue, ou un désintérêt lors des séances de cette semaine. Si c’est le cas, expliquez leur que les tableaux 2D sont la base essentielle des sujets de projets qui vont arriver. N’hésitez pas aussi à leur dire dès le départ que les tableaux 2D peuvent représenter beaucoup d’objets (images, photos, écrans d’ordi, écran de smartphone….); ça les motive un peu!

Pour ceux qui ont vraiment du mal, n’hésitez pas à aller les voir et les encourager à bien reprendre chez eux les TD/TP des semaines précédentes. Dites Leur que tout n’est pas perdu mais il va falloir bosser.

Exercice 1 : Échauffement

On considère le tableau d’entiers à deux dimensions suivant :

vector<vector<int>> t={{7, -1, 4, 3}, {15, 11, 17, 12}, {20, 34, 42, 25}};

  1. Quelles sont les valeurs t[0][0], t[0][1], et t[2][3] ?

    /// BEGIN SOLUTION

    Les valeurs sont : 7, -1, 25.

    /// END SOLUTION

  2. Donnez le nombre de lignes et de colonnes du tableau t.

    /// BEGIN SOLUTION

    Le tableau a trois lignes et quatre colonnes.

    /// END SOLUTION

Exercice 2 : Déclaration, allocation et initialisation de tableau 2D

Écrivez un fragment de programme qui construit un tableau 2D résultat de L lignes et C colonnes et qui l’initialise avec un entier v dans chaque case (on supposera L, C et v prédéfinis).

/// BEGIN SOLUTION

    vector<vector<int>> résultat;              // Définition
    résultat = vector<vector<int>>(L);         // Allocation
    for ( int i = 0; i < résultat.size(); i++ ) {
        résultat[i] = vector<int>(C);    //Allocation des sous-tableaux
    }
    for ( int i = 0; i < résultat.size(); i++ ) { //initialisation
        for ( int j = 0; j < résultat[i].size(); j++ ) {
            résultat[i][j] = v;
        }
    }

/// END SOLUTION

Exercice 3 : Opérations sur tableaux à deux dimensions

Dans cet exercice on considère des tableaux de caractères à deux dimensions. Par exemple l’un des tableaux suivants, respectivement carré tc, rectangulaire tr ou quelconque tq :

vector<vector<char>> tc = { {'P','o','u','r'}, {'b','i','e','n'}, {'r','i','r','e'}, {'l','i','s','!'} };   
vector<vector<char>> tr = { {'B','r','a','v','o'}, {'b','o','n','n','e'}, {'A','N','N','E','E'}        };
vector<vector<char>> tq = { {'T','o','u','t'}, {'v','a'}, {'m','i','e','u','x'}                        };

Pour chaque opération ci-dessous, spécifiez et définissez une fonction qui la réalise (elle prendra en paramètre un tableau t à deux dimensions, et éventuellement d’autres paramètres) :

  1. renvoyer le nombre de lignes de t.

    /// BEGIN SOLUTION

    /** renvoie le nombre de lignes du tableau
*@param t tableau de caractères à deux dimensions
*@return l'entier correspondant à son nombre de lignes
**/
int nombreDeLignes(vector<vector<char>> t) {
    return t.size();
}

    /// END SOLUTION

  2. renvoyer le nombre de colonnes de t (supposé rectangulaire).

    /// BEGIN SOLUTION

    /** renvoie le nombre de colonnes du tableau
* supposé rectangulaire
*@param t tableau de caractères rectangulaire à deux dimensions
*@return l'entier correspondant à son nombre de colonnes
*/
int nombreDeColonnes(vector<vector<char>> t) {
    if (t.size()==0) return 0;
    return t[0].size();
}

    /// END SOLUTION

  3. afficher les éléments de la ligne d’indice \(\ell\) de t.

    /// BEGIN SOLUTION

    /** affiche, en ligne, les éléments de la ligne d'indice l
*@param t tableau de caractères à deux dimensions
*@param l entier l'indice de la ligne à afficher
**/
void afficheLigne(vector<vector<char>> t, int l) {
    cout << "ligne d'indice " << l << " : " << endl;
    for (int colonne = 0; colonne < t[l].size() ; colonne++) {
        cout << t[l][colonne] << " ";
    }
    cout << endl;
}

    /// END SOLUTION

  4. afficher les éléments de la colonne d’indice \(c\) de t (supposé rectangulaire).

    /// BEGIN SOLUTION

    /** affiche, en colonne, les éléments de la colonne d'indice c
*@param t tableau de caractères à deux dimensions
*@param c entier  l'indice de la colonne à afficher
*/
void afficheColonne(vector<vector<char>> t, int c) {
    cout << "colonne d'indice " << c << " : " << endl;
    for (int ligne = 0; ligne < t.size() ; ligne++) {
        cout << t[ligne][c] << endl;
    }
    cout << endl; // aeration de l'affichage
}

    /// END SOLUTION

  5. afficher les éléments de la diagonale de t (supposé carré).

    /// BEGIN SOLUTION

    Première correction possible :

    /** affiche, en diagonale, les éléments de la première diagonale
*@param t tableau de caractères carré à deux dimensions
*/
void afficheDiagonaleEnDiagonale(vector<vector<char>> t) {
    cout << "Diagonale  : " << endl;
    for (int numLigne = 0; numLigne < t.size() ; numLigne++) {
        for ( int numColonne = 0;
              numColonne < t[numLigne].size();
              numColonne++
            ) {
            if (numLigne == numColonne) {
                cout << t[numLigne][numColonne] << " "; //affichage
            } else {
                cout << "   "; // espaces pour cacher les non affichés
            }
        }
        cout << endl;          // changement de ligne
    }
    cout << endl;             // aération de l'affichage
}

    Deuxième correction possible :

    /** affiche, en ligne, les éléments de la première diagonale
*@param t tableau de caractères carré à deux dimensions
*/
void afficheDiagonaleEnLigne(vector<vector<char>> t) {
    cout << "Diagonale  : " << endl;
    for (int numeroElement = 0; numeroElement < t.size() ; numeroElement++) {
        cout<< t[numeroElement][numeroElement]<<" ";
    }
    cout << endl;             // aération de l'affichage
}

    /// END SOLUTION

  6. afficher les éléments de t; pour t=tc, tr et tq, les affichages seraient respectivement :

    Pour          Bravo          Tout
bien          bonne          va
rire          ANNEE          mieux 
lis!

    /// BEGIN SOLUTION

    /** affiche les éléments du tableau, sans espacement
*@param t tableau de caractères à deux dimensions
**/
void affiche(vector<vector<char>> t) {
    for (int numLigne = 0; numLigne < t.size() ; numLigne++) {
        for (int numColonne = 0; numColonne < t[numLigne].size() ;
             numColonne++
            ) {
            cout << t[numLigne][numColonne];
        }
        cout << endl; // passage à la ligne
    }
    cout << endl;  //ligne après l(affichage)
}

    Ou mieux, en utilisant une boucle for each :

    /** affiche les éléments du tableau, sans espacement
*@param t tableau de caractères à deux dimensions
**/
void afficheForEach(vector<vector<char>> t) {
    for (auto ligne: t) {
        for (auto caractere: ligne) {
            cout << caractere;
        }
        cout << endl;
    }
}

    /// END SOLUTION

  7. indiquer si oui ou non, t contient le caractère c.

    /// BEGIN SOLUTION

    /** indique si un element est présent dans un tableau
*@param c caractère à rechercher
*@param t tableau de caractères à deux dimensions
**/
bool appartient(char c, vector<vector<char>> t) {
    for (int ligne = 0; ligne < t.size() ; ligne++) {
        for (int colonne = 0; colonne < t[ligne].size() ; colonne++) {
            if ( c == t[ligne][colonne] ) {
                return true;
            }
        }
    }
    return false;
}

    /// END SOLUTION

Exercice 4 : Matrices

Pour être plus spécifique et éviter d’avoir à écrire vector<vector<int>> à tout bout de champ, on peut définir un raccourci. Dans les questions suivantes qui traitent de matrices, on utilisera par exemple le raccourci suivant :

using Matrice = vector<vector<int>>;

Les deux constructions suivantes sont alors totalement équivalentes :

vector<vector<int>> tab = { {1,2,3}, {4,5,6}, {7,8,9} };
Matrice tab = { {1,2,3}, {4,5,6}, {7,8,9} };

Spécifiez et définissez une fonction pour chacune des questions suivantes :

  1. teste si un tableau carré est symétrique, i.e. si \(T_{i, j} = T_{j, i}\) pour tous \(i\) et \(j\).

    /// BEGIN SOLUTION

    /** Teste si une matrice est symétrique
 * @param t une matrice carrée
 * @return true si t[i][j] == t[j][i] pour tout i,j, false sinon
 **/
bool estSymétrique(Matrice t) {
    /// BEGIN SOLUTION
    for ( int i = 0; i < t.size(); i++ ) {
        for ( int j = 0; j < i; j++ ) {
            if ( t[i][j] != t[j][i] ) {
                return false;
            }
        }
    }
    return true;
    /// END SOLUTION
}

    Remarque : pour la deuxième boucle for, on aurait aussi pu écrire : for ( int j = 0; j < t.size(); j++ ) ce qui serait correct mais moins efficace. En effet on ferait deux fois chaque test. Par exemple, on testerait que t[0][1]=t[1][0] et que t[1][0]=t[0][1].

    /// END SOLUTION

  2. \(\clubsuit\) teste si une matrice est carrée et symétrique.

    /// BEGIN SOLUTION

    La spécification est importante. En effet, la fonction estSymétrique ne doit être appellée que sur des matrices carrées tandis que estCarréeSymétrique peut elle être appelée sur n’importe quelle matrice. On le voit bien sur les tests :

    void estSymétriqueTest() {
    CHECK(     estSymétrique(matriceVide) );
    CHECK( not estSymétrique(matriceCarrée) );
    CHECK(     estSymétrique(matriceSymétrique) );
    CHECK( not estSymétrique(matriceProduit) );
}

    void estCarréeSymétriqueTest() {
    CHECK(     estCarréeSymétrique(matriceVide) );
    CHECK( not estCarréeSymétrique(matriceCarrée) );
    CHECK(     estCarréeSymétrique(matriceSymétrique) );

    CHECK( not    estCarréeSymétrique(matriceRectangulaire) );
    CHECK( not    estCarréeSymétrique(matriceBizzare) );

}

    L’une ne considère en entrée que des matrices carrées, l’autre des matrices de toutes les formes. Dans l’état actuel de la programmation de estSymétrique, si elle est appelée avec une matrice hors spécification, comme renvoie une réponse erronée. Ceci induit que matriceBizzare pourrait être traité par l’appelant comme une matrice symétrique. Ce qui n’est pas le cas pour estCarréeSymétrique.

    /** Teste si une matrice est symétrique
 * @param t une matrice
 * @return true si la matrice est carrée et symétrique
 * cad t[i][j] == t[j][i] pour tout i,j, false sinon
 **/

bool estCarréeSymétrique(Matrice t) {
    /// BEGIN SOLUTION
    int taille = t.size();
    for ( int i = 0; i < taille; i++ )
        if ( t[i].size() != taille )
            return false;

    for ( int i = 0; i < taille; i++ )
        for (int j = 0; j < i; j++)
            if ( t[i][j] != t[j][i] )
                return false;

    return true;
    /// END SOLUTION
}

    /// END SOLUTION

  3. calcule la somme de deux matrices (supposées de mêmes dimensions). On vous rappelle que la somme de deux matrices \(T\) et \(T'\) est une matrice \(C\), où \(C_{i,j}=T_{i,j}+T'_{i,j}\) pour tous \(i\) et \(j\).

    /// BEGIN SOLUTION

    /** somme deux matrices dont les dimensions sont identiques
 * @param t1 une matrice
 * @param t2 une matrice
 * @return la matrice t1 + t2
 **/
Matrice somme(Matrice t1, Matrice t2) {
    /// BEGIN SOLUTION
    // Déclaration
    Matrice res;
    // Allocation
    res = Matrice(t1.size());
    // Allocation des sous-tableaux
    for ( int i = 0; i < t1.size(); i++ ) {
        res[i] = vector<int>(t1[i].size());
    }
    // Initialisation
    for ( int i = 0; i < res.size(); i++ ) {
        for ( int j = 0; j < res[i].size(); j++ ) {
            res[i][j] = t1[i][j] + t2[i][j];
        }
    }
    return res;
    /// END SOLUTION
}

    /// END SOLUTION

  4. \(\clubsuit\) calcule le produit de deux matrices. On vous rappelle que le produit de deux matrices \(T\) et \(T'\) est une matrice \(C\), où \(C_{i,j}=T_{i,1}T'_{1,j}+ T_{i,2}T'_{2,j} + \cdots\).

    /// BEGIN SOLUTION

    /** produit de deux matrices dont les dimensions sont compatibles
 * @param t1 une matrice
 * @param t2 une matrice
 * @return la matrice t1 * t2 (produit matriciel)
 **/
Matrice produit(Matrice t1, Matrice t2) {
    /// BEGIN SOLUTION
    Matrice res;
    res = Matrice(t1.size());
    for ( int i = 0; i < t1.size(); i++ ) {
        res[i] = vector<int>(t2[0].size());
    }
    for ( int i = 0; i < res.size(); i++ ) {
        for ( int j = 0; j < res[i].size(); j++ ) {
            res[i][j] = 0;
            for ( int k = 0; k < t2.size(); k++ ) {
                res[i][j] += t1[i][k] * t2[k][j];
            }
        }
    }
    return res;
    /// END SOLUTION
}

    Remarque : Si t1 est de taille \(n \times p\) et t2 de taille \(p \times m\) alors res doit être de taille \(n \times m\) i.e. t1.size() \(\times\) t2[0].size(). De plus la somme pour calculer un coefficient de res porte sur \(p\) éléments, soit t2.size().

    /// END SOLUTION

Exercice 5 : Réservation de salle

Une salle de réunion peut être utilisée par les employés d’une entreprise. La réservation se fait par plages d’une heure, de 8h00 à 19h00, chaque plage horaire commençant à l’heure pile; par exemple, il y a une plage 9h00-10h00 mais il n’y a pas de plage 9h15-10h15. Le planning hebdomadaire de la salle est modélisé par un tableau de booléens à deux dimensions: cinq lignes correspondant aux cinq jours de la semaine, onze colonnes correspondant aux onze plages horaires de la journée. La valeur pour un jour et une plage horaire donnée est true si la salle est réservée sur cette plage horaire, et false si elle est libre. On suppose pour la suite de l’exercice avoir accès au tableau suivant :

vector<string> jours = {"lundi", "mardi", "mercredi", "jeudi", "vendredi"};

  1. Définissez une fonction qui construit un planning vide.

    /// BEGIN SOLUTION

    On suppose avoir à disposition les constantes suivantes:

    int nbPlagesHoraires = 11;
int nbJours = 5;
int decalagePremiereHeure = 8;

    /** créé un planning vide
 **/
Planning creationPlanning() {
    /// BEGIN SOLUTION
    // Déclaration
    Planning planning;
    // Allocation
    planning = Planning(nbJours);
    // Allocation des sous-tableaux
    for (int jour = 0; jour < nbJours; jour++) {
        planning[jour] = vector<bool> (nbPlagesHoraires);

    }
    // Initialisation
    for (int numJour = 0; numJour < nbJours; numJour++) {
        for ( int numPlage = 0;
                  numPlage < nbPlagesHoraires;
                  numPlage++ ) {
            planning[numJour][numPlage] = false;
        }
    }
    return planning;
    /// END SOLUTION
}

    /// END SOLUTION

  2. Définissez une fonction qui prend en paramètre le planning de réservation d’une salle et qui l’affiche de façon intelligible :

    1. avec des phrases (par exemple : salle réservée le mardi de 9h00 à 10h00).

      /// BEGIN SOLUTION

      /** Affiche en mode textuel mais lisible le planning d'occupation
* (par exemple en faisant la liste des horaires de reservations)
* @param planning un tableau de nbJours*nbPlagesHoraires booléens
*/


void affichePlanning(Planning planning) {
    /// BEGIN SOLUTION
    for (int numJour = 0; numJour < nbJours; numJour++) {
        cout << endl;
        cout << jours[numJour] << endl;
        cout << "______________" << endl;

        for (   int numPlage = 0;
                numPlage < nbPlagesHoraires;
                numPlage++ ) {
            if (planning[numJour][numPlage]) {
                cout << " Salle réservée le " << jours[numJour];
                cout << " de " << numPlage + decalagePremiereHeure;
                cout << " heures à ";
                cout << numPlage + 1 + decalagePremiereHeure;
                cout << " heures." << endl;
            }
        }
    }
    /// END SOLUTION
}

      /// END SOLUTION

    2. \(\clubsuit\) sous la forme d’une grille jour / plage horaire, où le mot «Réservée» figure dans les cases concernées.

      /// BEGIN SOLUTION

      /** (trèfle) affiche un planning sous la forme d'une "grille".
* Chaque colonne commence par le nom du jour representé,
* chaque ligne commence par la plage horaire representée.
* Le mot "Réservé" apparaît sur les plages réservées
* et les autres apparaissent en blanc.
* On pourra utiliser les symboles '|' et '_' pour tracer des lignes
* On pourra aussi utiliser la fonction afficheCaractere
*@param planning: tableau de booléens: le planning à afficher
*/

void affichePlanningGrille(Planning planning) {
    /// BEGIN SOLUTION
    int longueurCellule = 12;
    int nbEspaces = 0;
    cout << endl;
    afficheCaractere('-', 90);
    cout << endl;
    afficheCaractere(' ', longueurCellule + 6);
    afficheCaractere('|', 1);
    for (int numJour = 0; numJour < nbJours; numJour++) {
        afficheCaractere('|', 1);
        afficheCaractere(' ', 2);
        cout << jours[numJour];
        nbEspaces = longueurCellule - jours[numJour].size() - 2;
        afficheCaractere(' ', nbEspaces);
        afficheCaractere('|', 1);
    }
    afficheCaractere('|', 1);
    cout << endl;
    afficheCaractere('-', 90);
    cout << endl;
    for ( int numPlage = 0;
          numPlage < nbPlagesHoraires;
          numPlage++) {
        if (numPlage + decalagePremiereHeure < 10) {
            cout << " ";
        }
        if (numPlage + decalagePremiereHeure + 1 < 10) {
            cout << " ";
        }
        cout << " de " ;
        cout << numPlage + decalagePremiereHeure << " h à ";
        cout << numPlage + decalagePremiereHeure +1 << " h   ";
        afficheCaractere('|', 1);
        for (int numJour = 0; numJour < nbJours; numJour++) {
            afficheCaractere('|', 1);
            if (planning[numJour][numPlage]) {
                afficheCaractere(' ', 2);
                cout << "Réservée";
                afficheCaractere(' ', 2);
            } else {
                nbEspaces = longueurCellule - 1;
                afficheCaractere(' ', longueurCellule);
            }
            afficheCaractere('|', 1);
        }
        afficheCaractere('|', 1);
        cout << endl;
        afficheCaractere('-', 90);
        cout << endl;
    }
    cout << endl;
    /// END SOLUTION
}

      /// END SOLUTION

  3. Définissez une fonction, avec son test, qui calcule le taux d’occupation d’une salle, c’est à dire le nombre de plages réservées divisé par le nombre total de plages.

    /// BEGIN SOLUTION

    /** calcule le taux d'occupation en pourcentage de la salle
* dont on transmet le planning sous forme codé.
* @param planning un tableau de nbJours*nbPlagesHoraires
* booléens supposé rectangulaire car cree avec creationPlanning()
* qui code la prévision d'occupation de la salle concernée
* true: la salle est réservée sur la plage horaire concernée,
* false : la salle est libre à l'heure codée.
* @return le taux d'occupation en pourcentage
* C'est à dire le nombre de réservations dans le planning
* divisé par le nombre de plages de réservations possibles
* (normalement nbJours*nbPlagesHoraires)
*/
double tauxOccupation(Planning planning) {
    /// BEGIN SOLUTION
    int nbReservations = 0;
    for (int numJour = 0;
             numJour < nbJours;
             numJour++
        ) {
        for (int numPlage = 0;
                 numPlage < nbPlagesHoraires;
                 numPlage++) {
            if (planning[numJour][numPlage]) {
                nbReservations++;
            }
        }
    }
    return 100. * nbReservations / (nbJours * nbPlagesHoraires);
    /// END SOLUTION
}

    void tauxOccupationTest() {
    double precision = 0.01;

    //une salle entièrementLibre
    Planning salleVide =        creationPlanning();
    CHECK(  abs(tauxOccupation( salleVide ) - 0) < precision);

    //une salle presque entièrementLibre
    Planning salle306 =         creationPlanning();
    //réservations
    salle306[1][2] = true;
    salle306[1][1] = true;
    CHECK( abs(tauxOccupation( salle306         ) - 100.*2/11/5) < precision);

    //une salle quelconque
    Planning salleRose =        creationPlanning();
    for (int j = 0; j < nbJours; j++) {
        for (int p = 0; p < nbPlagesHoraires; p++) {
            if (p % 2 == 1) {
                salleRose[j][p] = false;
            } else        {
                salleRose[j][p] = true;
            }
        }
    }
    CHECK( abs(tauxOccupation( salleRose      ) -  100.*6/11) < precision);
    
    // une salle très occupée
    Planning salleTresOccupee = creationPlanning();
    for (int j = 0; j < nbJours; j++) {
        for (int p = 0; p < nbPlagesHoraires; p++) {
            salleTresOccupee[j][p] = true;
        }
    }
    CHECK( abs(tauxOccupation( salleTresOccupee ) - 100) < precision);

}

    /// END SOLUTION

Exercice 6 : \(\clubsuit\) Le jeu du démineur

L’objectif de cet exercice est de réaliser une version simple du jeu du démineur. Dans ce jeu, le joueur doit localiser des mines cachées dans un champ virtuel avec pour seule indication le nombre de mines dans les zones adjacentes. Le champ consiste en une grille rectangulaire dont chaque case contient ou non une mine. Au départ, le contenu de chaque case est masqué. À chaque étape, le joueur peut :

  • Démasquer le contenu d’une case; s’il y a une mine, « BOUM! », il a perdu. Sinon, le nombre de cases adjacentes (y compris en diagonale) contenant une mine est affiché.

  • Marquer une case, s’il pense qu’elle contient une mine.

Le joueur a gagné lorsqu’il a démasqué toutes les cases ne contenant pas de mine.

Pour représenter en mémoire l’état interne de la grille, on utilisera un tableau à deux dimensions de caractères (type vector<vector<char>>). On utilisera les conventions suivantes pour représenter l’état d’une case :

  • “m”: présence d’une mine, “M”: présence d’une mine, case marquée;

  • “o”: absence de mine, “O”: absence de mine, case marquée;

  • “ “: absence de mine, case démasquée.

Afin d’éviter d’avoir à écrire vector<vector<char>> à tout bout de champ on utilise un raccourci :

using GrilleDemineur = vector<vector<char>>; // tableau 2D de caractères

  1. Définissez une fonction permettant de compter le nombre total de mines (marquées ou pas) dans une grille.

    /// BEGIN SOLUTION

    On va parcourir la grille, représentée par un tableau 2D :

    /** Compte le nombre de mines dans une grille
 * @param grille un tableau 2D de caractères (vector<vector<char> >)
 * @return le nombre de mines dans grille
 **/
int nombreMines(GrilleDemineur grille) {
    /// BEGIN SOLUTION
    int compteur = 0;
    for (int i = 0; i < grille.size(); i++)
        for (int j = 0; j < grille[i].size(); j++)
            if (grille[i][j] == 'm' or grille[i][j] == 'M')
                compteur++;
    return compteur;
    /// END SOLUTION
}

    /// END SOLUTION

  2. Définissez une fonction permettant de tirer au hasard une grille initiale. On supposera fournie une fonction bool boolAleatoire() renvoyant un booléen tiré au hasard.

    /// BEGIN SOLUTION

    /** Construit une grille initiale
 * @param n un entier positif
 * @param m un entier positif
 * @return un tableau de caractères de n lignes et m colonnes rempli
 *  aléatoirement et ne contenant que des 'm' ou 'o'
 **/
GrilleDemineur grilleInitiale(int n, int m) {
    /// BEGIN SOLUTION
    // Déclaration
    GrilleDemineur result;
    // Allocation
    result = GrilleDemineur(n);
    // Allocation des sous-tableaux
    for (int i = 0; i < n; i++)
        result[i] = vector<char>(m);
    // Initialisation
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (boolAleatoire())
                result[i][j] = 'm';
            else
                result[i][j] = 'o';
        }
    }
    return result;
    /// END SOLUTION
}

    /// END SOLUTION

  3. Définissez une fonction permettant de tester si une grille est gagnante.

    /// BEGIN SOLUTION

    On gagne la partie lorsque toutes les cases non minées sont démasquées:

    /** Teste si une grille est gagnante
 * @param grille un tableau 2D de caractères (vector<vector<char> >)
 * @return un booléen vrai si grille est une grille gagnante, ie si
 *  toutes les cases qui ne sont pas des mines ont été démasquées
 **/
bool grilleEstGagnante(GrilleDemineur grille) {
    /// BEGIN SOLUTION
    for (int i = 0; i < grille.size(); i++) {
        for (int j = 0; j < grille[i].size(); j++) {
            if (grille[i][j] == 'O' or grille[i][j] == 'o') {
                return false;
            }
        }
    }
    return true;
    /// END SOLUTION
}

    /// END SOLUTION

  4. Définissez une fonction permettant de compter le nombre de mines dans les cases adjacentes à une case donnée d’une grille.

    /// BEGIN SOLUTION

    Il suffit de parcourir les huit cases adjacentes et de compter le nombre de M et m :

    /** Renvoie le nombre de mines voisines à ième ligne, jème colonne
 * @param grille un tableau 2D de caractères (vector<vector<char> >)
 * @param i un entier décrivant une ligne de grille
 * @param j un entier décrivant une colonne de grille
 * @return un entier entre 0 et 8 comptant le nombre de mines
 *  adjacentes à grille[i][j]
 **/
int minesVoisines(GrilleDemineur grille, int i, int j) {
    /// BEGIN SOLUTION
    int resultat = 0;
    int n = grille.size();
    int m = grille[0].size();
    for (int i1 = max(i - 1, 0) ; i1 <= min(i + 1, n - 1); i1++ ) {
        for (int j1 = max(j - 1, 0); j1 <= min(j + 1, m - 1); j1++ ) {
            if (grille[i1][j1] == 'm' or grille[i1][j1] == 'M') {
                resultat++;
            }
        }
    }
    if (grille[i][j] == 'm' or grille[i][j] == 'M')
        resultat--;
    return resultat;
    /// END SOLUTION
}

    Remarque : pour simplifier la boucle, au lieu de compter uniquement dans les 8 cases adjacentes, on compte dans 9 cases (en comptant la case elle-même), puis si besoin on enlève ce qui a été compté en trop.

    /// END SOLUTION

  5. Définissez une fonction permettant de renvoyer une chaîne de caractères représentant la grille telle que doit la voir le joueur.

    /// BEGIN SOLUTION

    /** Dessine une grille
 * @param grille un tableau 2D de caractères (vector<vector<char> >)
 * @return une chaîne de caractères (string) décrivant la grille de
 *  gauche à droite et de bas en haut, avec un saut de la ligne après
 *  chaque ligne de la grille
 *
 * Indications:
 * - si s et t sont des chaînes de caractères, s+t est leur concaténation
 * - "\n" représente un saut de ligne
 **/
string dessinGrille(GrilleDemineur grille) {
    /// BEGIN SOLUTION
    string resultat;
    for (int i = 0; i < grille.size(); i++) {
        for (int j = 0; j < grille[i].size(); j++) {
            char c = grille[i][j];
            if (c == 'M' or c == 'O')
                resultat = resultat + "M";
            else if (c == ' ')
                resultat += minesVoisines(grille, i, j) + '0';
            else
                resultat = resultat + " ";
        }
        resultat = resultat + "\n";
    }
    return resultat;
    /// END SOLUTION
}

    /// END SOLUTION