Doublons et grille de démineur - Sujet 28 - EP NSI 2025

Exercice 1

EXERCICE 1 (10 points)

Écrire une fonction a_doublon qui prend en paramètre un tableau trié de nombres dans l’ordre croissant et renvoie True si ce tableau contient au moins deux nombres identiques, False sinon.

Exemple :

>>> a_doublon([])
False
>>> a_doublon([1])
False
>>> a_doublon([1, 2, 4, 6, 6])
True
>>> a_doublon([2, 5, 7, 7, 7, 9])
True
>>> a_doublon([0, 2, 3])
False

Exercice 2

EXERCICE 2 (10 points)

On souhaite générer des grilles du jeu de démineur à partir de la position des bombes à placer. On se limite à la génération de grilles carrées de taille $n \times n$ où $n$ est le nombre de bombes du jeu.

Dans le jeu du démineur, chaque case de la grille contient soit une bombe, soit une valeur qui correspond aux nombres de bombes situées dans le voisinage direct de la case (au-dessus, en dessous, à droite, à gauche ou en diagonale : chaque case a donc 8 voisins si elle n’est pas située au bord de la grille).

Un exemple de grille $5 \times 5$ de démineur dans laquelle la bombe est représentée par une étoile est représenté ci-dessous.

[Figure : grille 5 × 5 du démineur, les bombes étant représentées par une étoile]


1	1	1	0	0
1	*	1	1	1
2	2	3	2	*
1	*	2	*	3
1	1	2	2	*

On utilise une liste de listes pour représenter la grille et on choisit de coder une bombe par la valeur -1.

L’exemple ci-dessus sera donc codé par la liste :

[[1,  1, 1,  0,  0],
 [1, -1, 1,  1,  1],
 [2,  2, 3,  2, -1],
 [1, -1, 2, -1,  3],
 [1,  1, 2,  2, -1]]

Compléter le code situé à la page suivante afin de générer des grilles de démineur, on pourra vérifier que l’appel

genere_grille([(1, 1), (2, 4), (3, 1), (3, 3), (4, 4)])

renvoie bien la liste donnée en exemple.

def voisinage(n, ligne, colonne):
    """ Renvoie la liste des coordonnées des voisins de la case
    (ligne, colonne) dans un grille de taille n x n,
    en tenant compte des cases sur les bords. """
    voisins = []
    for dl in range(-1, 2):
        for dc in range(-1, 2):
            l = ligne + dl
            c = colonne + dc
            if (l, c) != (ligne, colonne) \
                    and 0 <= l < n and 0 <= c < n:
                voisins.append((l,c))
    return voisins

def incremente_voisins(grille, ligne, colonne):
    """ Incrémente de 1 toutes les cases voisines d'une bombe."""
    voisins = ...
    for l, c in voisins:
        if grille[l][c] != ...: # si ce n'est pas une bombe
            ...  # on ajoute 1 à sa valeur

def genere_grille(bombes):
    """ Renvoie une grille de démineur de taille nxn où n est
    le nombre de bombes, en plaçant les bombes à l'aide de
    la liste bombes de coordonnées (tuples) passée en
    paramètre. """
    n = len(bombes)
    # Initialisation d'une grille nxn remplie de 0
    grille = [[0 for colonne in range(n)] for ligne in range(n)]
    # Place les bombes et calcule les valeurs des autres cases
    for ligne, colonne in bombes:
        grille[ligne][colonne] = ... # place la bombe
        ...  # incrémente ses voisins
    return grille

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

tab est une liste d’entiers, éventuellement vide : 0 <= len(tab) <= 2*10^5
-10^9 <= tab[i] <= 10^9
tab est trié dans l’ordre croissant (au sens large : deux éléments consécutifs peuvent être égaux)
la fonction renvoie un booléen True ou False
une solution en O(n^2) (comparaison de toutes les paires) dépassera la limite de temps

Exercice 2

Contraintes :

bombes est une liste non vide de tuples (ligne, colonne) d’entiers : 1 <= len(bombes) <= 200
on note n = len(bombes) ; la grille renvoyée est de taille n x n
0 <= ligne < n et 0 <= colonne < n pour chaque tuple de bombes
les coordonnées de bombes sont deux à deux distinctes
la valeur renvoyée est une liste de n listes de n entiers, une bombe étant codée par -1 et toute autre case par son nombre de bombes voisines (entre 0 et 8)

Énoncé du problème

Exercice 1

Exercice 2