Bender - Episode 1 – solution CodinGame en C
On simule Bender déplacement par déplacement : on garde sa position, sa direction, le mode breaker et l'inversion des priorités, et quand la case devant lui est bloquée on essaie SOUTH, EAST, NORTH, WEST (ou l'inverse) dans l'ordre. Pour afficher LOOP de façon fiable, on enregistre chaque état (x, y, direction, breaker, inversé) rencontré et on s'arrête dès qu'un état se répète, en vidant cet historique à chaque mur cassable détruit puisque la carte a changé.
L'énoncé
Bender démarre sur la case '@' d'une carte d'au plus 100x100 cases, d'abord orienté vers le sud, et doit atteindre la cabine de suicide '$'. Les murs '#' l'arrêtent toujours, les murs 'X' l'arrêtent sauf en mode breaker, où il les pulvérise. Les lettres S, E, N, W imposent une nouvelle direction, 'B' bascule le mode breaker (bière), 'I' inverse son ordre de priorité, et les deux cases 'T' le téléportent l'une vers l'autre.
Chaque fois que la case devant lui est bloquée, il essaie les directions dans l'ordre de priorité (SOUTH, EAST, NORTH, WEST, ou WEST, NORTH, EAST, SOUTH une fois inversé) et prend la première libre. On affiche chacun de ses déplacements jusqu'à ce qu'il atteigne '$', ou le seul mot LOOP s'il doit errer indéfiniment.
La démarche, étape par étape
- Lire la carte et repérer les cases spécialesOn lit chaque rangée comme une ligne complète, car elles contiennent des espaces. On note la position de départ et les coordonnées des deux téléporteurs, et on remplace '@' par une case vide pour qu'il ne soit pas traité comme un obstacle plus tard.
- Choisir la direction du tourOn conserve la direction courante tant que la case suivante est libre. Ce n'est que lorsqu'elle est bloquée qu'on parcourt la liste de priorité depuis le début ; ce n'est pas une règle « tourner à droite », Bender repart toujours de SOUTH (ou de WEST en mode inversé).
- Avancer, puis appliquer l'effet de la caseOn avance d'une case, on journalise le déplacement, puis on réagit à la case d'arrivée : une lettre de direction fixe la direction, B et I basculent leurs indicateurs, T saute vers l'autre téléporteur en gardant la direction, et un X (atteignable seulement en mode breaker) devient une case vide.
- Détecter les boucles avec un ensemble d'étatsAvant chaque déplacement, on vérifie si le tuple (x, y, direction, breaker, inversé) a déjà été vu. Si oui, la simulation étant déterministe et la carte inchangée, il répétera la même chose à l'infini : on affiche LOOP et on s'arrête.
- Réinitialiser l'historique quand la carte changeCasser un mur X modifie la carte, donc un état répété après coup ne prouve plus une boucle. Vider l'ensemble des états visités à chaque mur détruit garde une détection exacte ; il y a au plus L·C murs, donc le travail total reste borné.
Complexité
O(S·K)O(L·C)S = 16·L·C états possibles et K le nombre de murs X cassés plus un ; en pratique le chemin est court. La table des états visités compte 16 entrées par case (4 directions × breaker × inversé).
Code de la solution
Bender - Episode 1 – C
#include <stdio.h>
#include <string.h>
// direction indexes: 0 SOUTH, 1 EAST, 2 NORTH, 3 WEST (default priority order)
static const int DX[4] = { 0, 1, 0, -1 };
static const int DY[4] = { 1, 0, -1, 0 };
static const char *NAMES[4] = { "SOUTH", "EAST", "NORTH", "WEST" };
static char map[100][102];
// seen[y][x][dir][breaker][inverted]: state already visited since the last broken wall
static unsigned char seen[100][100][4][2][2];
// worst case: every state once between each of the (at most L*C) broken walls
static int moves[1000000];
static int dirOf(char c)
{
switch (c) {
case 'S': return 0;
case 'E': return 1;
case 'N': return 2;
case 'W': return 3;
}
return -1;
}
static int blocked(int x, int y, int breaker)
{
char c = map[y][x];
return c == '#' || (c == 'X' && !breaker);
}
int main()
{
int L, C;
if (scanf("%d %d", &L, &C) != 2) return 0;
fgetc(stdin); // consume end of line
int x = 0, y = 0, tx[2], ty[2], nt = 0;
for (int i = 0; i < L; i++) {
fgets(map[i], sizeof map[i], stdin); // rows may contain spaces
for (int j = 0; j < C; j++) {
if (map[i][j] == '@') { x = j; y = i; map[i][j] = ' '; }
if (map[i][j] == 'T') { tx[nt] = j; ty[nt] = i; nt++; }
}
}
int dir = 0, breaker = 0, inverted = 0, n = 0;
while (map[y][x] != '$') {
if (seen[y][x][dir][breaker][inverted]) {
puts("LOOP");
return 0;
}
seen[y][x][dir][breaker][inverted] = 1;
// facing an obstacle: try the 4 directions in priority order
if (blocked(x + DX[dir], y + DY[dir], breaker)) {
for (int k = 0; k < 4; k++) {
int d = inverted ? 3 - k : k;
if (!blocked(x + DX[d], y + DY[d], breaker)) { dir = d; break; }
}
}
x += DX[dir];
y += DY[dir];
moves[n++] = dir;
char c = map[y][x];
if (c == 'X') { // only reachable in breaker mode
map[y][x] = ' ';
memset(seen, 0, sizeof seen); // the map changed, old states are no longer loops
} else if (c == 'B') {
breaker = !breaker;
} else if (c == 'I') {
inverted = !inverted;
} else if (c == 'T') {
int other = (x == tx[0] && y == ty[0]) ? 1 : 0;
x = tx[other];
y = ty[other];
} else if (dirOf(c) >= 0) {
dir = dirOf(c);
}
}
for (int i = 0; i < n; i++)
puts(NAMES[moves[i]]);
return 0;
}
Erreurs fréquentes
- Utiliser un compteur de coups comme détecteur de boucleToute limite fixe est soit trop petite pour les grandes cartes, soit une simple estimation. La répétition d'un état est le seul critère exact, et la borne qu'il faudrait sinon est d'environ 16·L·C par mur cassé.
- Tourner par rapport à la direction couranteQuand il est bloqué, Bender ne tourne ni à droite ni à gauche : il reparcourt toute la liste de priorité depuis sa première entrée. Partir de la direction courante donne de mauvais chemins sur les tests « obstacles ».
- Oublier que la téléportation conserve la directionAprès être arrivé sur un T, Bender apparaît sur l'autre T et continue dans le même sens. Il ne faut pas réappliquer la téléportation à l'arrivée, sinon il rebondit entre les deux à l'infini.
- Ne pas réinitialiser la détection après un mur casséSi on conserve les anciens états après avoir pulvérisé un X, un nouveau passage par la même case ressemble à une boucle alors que la carte est différente. Les tests de type « mur cassé » sont conçus précisément pour attraper cette erreur.
- Lire les rangées avec une fonction de lecture par motLes rangées sont pleines d'espaces, donc scanf("%s"), cin >> ou split() perdent des cases. Il faut lire la ligne entière.
Pour aller plus loin
La raison pour laquelle l'ensemble d'états doit contenir les indicateurs breaker et inversé, mais pas l'historique des déplacements, est que Bender est un automate fini déterministe sur une carte fixe : son action suivante ne dépend que de (position, direction, breaker, inversé) et de l'ensemble courant des murs X. Dès qu'un de ces tuples se répète avec les mêmes murs, l'avenir est une copie du passé. Comme les murs X ne peuvent que disparaître, jamais réapparaître, ils jouent le rôle d'un compteur monotone : vider l'ensemble des visités après chaque casse est sans risque, et la simulation termine à coup sûr en au plus (nombre de X + 1) × 16·L·C étapes. C'est une preuve, pas une heuristique, et c'est pourquoi cette méthode passe tous les validateurs quelle que soit la taille de la carte.
Questions fréquentes
Pourquoi ma solution Bender passe les tests mais échoue aux validateurs avec LOOP ?
En général parce que LOOP est décidé par une limite de coups ou par le simple retour sur une case. Il faut inclure la direction, le mode breaker et l'inversion des priorités dans l'état, et le réinitialiser quand un mur casse.
La case '@' bloque-t-elle Bender par la suite ?
Non, c'est un sol ordinaire une fois qu'il l'a quittée. On la remplace par un espace au moment de la lecture pour que le test d'obstacle ne la traite pas à part.
Bender peut-il casser les murs '#' en mode breaker ?
Non. Le mode breaker n'agit que sur les cases 'X' ; '#' déclenche toujours la recherche par priorité.