Corrigé Centrale 2025 Informatique MPI — Partie A, I (Q1 à Q6) : Rush Hour en C : états, plateau, listes de déplacements

Sujet officiel du concours Centrale, session 2025, épreuve Informatique MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Grille carrée de $M \times M$ cases $(i, j)$ , $i$ numéro de ligne, $j$ numéro de colonne ; la sortie est à droite de la ligne $S$ . Voitures ( $2$ cases) et camions ( $3$ cases) glissent d'une ou plusieurs cases vers l'avant ou l'arrière ; la voiture grise, seule voiture horizontale de la ligne $S$ , doit atteindre la sortie. Configuration de départ ( $M = 6$ , $S = 2$ ) :

Une solution en $9$ coups : $0$ recule d'une case (2.a) ; $4$ recule, $3$ et $1$ avancent de trois cases (2.b) ; $2$ avance de trois cases (2.c) ; $1$ , $3$ reculent et $4$ avance de trois cases, puis $2$ avance d'une case (2.d, position gagnante).


#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

#define M 6
#define MAX_V (M * M) / 2
#define S 2

struct vehicule_s {
    int i;
    int j;
    int longueur;
    char direction;
};
typedef struct vehicule_s vehicule;

struct etat_s {
    vehicule v[MAX_V];
    int n;
    int distance;
};
typedef struct etat_s etat;

$(i, j)$ est la case du véhicule la plus en haut à gauche, direction vaut 'H' ou 'V' ; v[k] décrit le véhicule $k$ pour $k < n$ , et distance est initialisé à $0$ .
Q1. etat *e_nouveau(void) (état sans véhicule) et void e_libere(etat *e).
Q2. bool e_egal(etat *e1, etat *e2) : même $n$ et mêmes véhicules d'indice $k$ (le champ distance est ignoré).
Q3. void e_ajoute_vehicule(int i, int j, int longueur, char direction, etat *e), avec une assertion garantissant $n ⩽$ MAX_V.


const int vide = -1;

struct plateau_s {
    int tab[M][M];
};
typedef struct plateau_s plateau;

Q4. plateau *p_etat(etat *e) : vide partout, sauf l'indice du véhicule sur chaque case occupée.


struct deplacement_s {
    int k;
    int pas;
    struct deplacement_s *suivant;
};
typedef struct deplacement_s deplacement;

Un maillon représente le déplacement du véhicule k de pas cases dans le sens des $i$ (ou des $j$ ) croissants ; la liste vide est NULL. On dispose de deplacement *e_deplacements(etat *e), liste des déplacements valides.
Q5. deplacement *d_cons(int k, int pas, deplacement *lst) : ajout en tête.
Q6. void d_libere(deplacement *lst).

Corrigé

Tout le code C de cette partie (et des parties II à IV) a été compilé ensemble (gcc -std=c11 -Wall -Wextra -fsanitize=undefined, sans avertissement) et exécuté sur la configuration de la figure, sur l'état vide et sur un plateau rempli de $18 =$ MAX_V voitures ; l'outil leaks de macOS ne signale aucune fuite à la fin du programme de test.

Ce que le correcteur attend : la structure etat contient le tableau v (ce n'est pas un pointeur) : un seul malloc(sizeof(etat)) réserve d'un coup les MAX_V véhicules, et un seul free rend le tout. Le rapport du jury signale que ce point a perturbé de nombreux candidats. Il en va de même de plateau, qui contient sa matrice.

Q1.


etat *e_nouveau(void) {
    etat *e = malloc(sizeof(etat));
    assert(e != NULL);
    e->n = 0;
    e->distance = 0;
    return e;
}

void e_libere(etat *e) {
    free(e);
}

L'état est alloué sur le tas, pour survivre à l'appel ; $n = 0$ dit qu'aucune case de v n'est significative, le contenu de v peut donc rester non initialisé. Les deux fonctions sont en $O (1)$ .

Q2. On compare d'abord les nombres de véhicules, puis les véhicules de même indice, champ par champ (l'opérateur == n'existe pas entre structures en C).


bool e_egal(etat *e1, etat *e2) {
    if (e1->n != e2->n) return false;
    for (int k = 0; k < e1->n; k++) {
        vehicule a = e1->v[k], b = e2->v[k];
        if (a.i != b.i || a.j != b.j || a.longueur != b.longueur
            || a.direction != b.direction)
            return false;
    }
    return true;
}

Invariant de la boucle : les véhicules d'indice $< k$ coïncident. On sort avec false dès une différence, avec true si tous coïncident ; le champ distance n'est jamais lu, comme demandé. Coût $O (n)$ . Exécuté : une copie de l'état de la figure dont on a changé distance lui est égale, elle ne l'est plus après avoir décalé la voiture $0$ .

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →