The Labyrinth – solution CodinGame en Java
On garde sa propre copie de la carte, remplie de '?' au départ, et on la met à jour chaque tour avec la vue 5x5. On explore d'abord : BFS répété vers la case inconnue la plus proche, en traitant les murs et la salle de contrôle comme bloqués. Quand il ne reste rien à découvrir, BFS vers la salle de contrôle, puis BFS de retour vers le départ ; la carte étant entièrement connue, le chemin de retour est le plus court et tient dans le compte à rebours de l'alarme. Chaque BFS est linéaire en taille de grille.
L'énoncé
Kirk se trouve quelque part dans un labyrinthe rectangulaire de R lignes et C colonnes et ne voit que les cases à deux pas de lui. Il doit trouver la salle de contrôle (C), y entrer, puis revenir à son point de départ (T) avant la fin d'un compte à rebours d'alarme de A tours.
À chaque tour, on reçoit la ligne et la colonne de Kirk ainsi que toute la grille, où les cases non vues sont des '?', les murs des '#' et le sol libre des '.'. On répond UP, DOWN, LEFT ou RIGHT. Le jetpack n'a du carburant que pour un nombre limité de déplacements : errer au hasard n'est pas une option.
La démarche, étape par étape
- Maintenir une carte persistanteOn stocke toutes les cases déjà vues. L'arbitre renvoie la grille à chaque tour, mais garder sa propre copie permet de raisonner sur tout le labyrinthe et de l'afficher sur stderr pour déboguer.
- Explorer par BFS vers le '?' le plus procheOn lance un BFS depuis Kirk sur les cases libres connues, en évitant '#' et 'C', et on s'arrête au premier '?' défilé. On suit le chemin seulement jusqu'à ce que cette case devienne visible, puis on relance la recherche : cette exploration gloutonne de la frontière gaspille très peu de déplacements.
- Ne jamais entrer dans C trop tôtEntrer dans la salle de contrôle déclenche l'alarme. Garder 'C' dans l'ensemble des cases bloquées pendant l'exploration garantit que le compte à rebours ne démarre que lorsqu'on est prêt.
- Aller à la salle de contrôleQuand aucun '?' accessible ne reste, la carte est entièrement connue. On fait un BFS vers 'C' à travers les cases connues (en bloquant '#' et '?') et on suit le chemin.
- Revenir au départUn BFS de C vers T sur la carte connue donne le chemin de retour le plus court possible, qui par construction des tests tient dans A déplacements. On le suit pour gagner.
Complexité
O(T · R · C)O(R · C)Chaque BFS est linéaire en taille de grille, et le code lance au plus un BFS par segment de déplacement, borné par les T tours que Kirk peut jouer. Les grilles font au plus 100x200, on est donc très loin des limites.
Code de la solution
The Labyrinth – Java
goTo(target, toAvoid, onlyReveal) est un BFS réutilisable : avec onlyReveal, il avance jusqu'à ce que le '?' cible soit vu, sinon jusqu'à ce que Kirk s'y trouve. La grille des prédécesseurs stocke un indice de direction, de sorte que (dir + 2) % 4 donne le déplacement à rejouer.
import java.util.*;
import java.io.*;
import java.math.*;
/** Class representing a couple of cartesian coordinates*/
class Coords {
int X, Y;
public Coords(int X, int Y){
this.X = X;
this.Y = Y;
}
/** returns an array containing the 4 adjacent coordinates to this */
public Coords[] neighbours() {
Coords res[] = {new Coords(X, Y-1), new Coords(X+1, Y), new Coords(X, Y+1), new Coords(X-1, Y)};
return res;
}
public boolean equals(Coords d) {
return this.X == d.X && this.Y == d.Y;
}
}
class Player {
/** height of the labyrinth*/
private static int height;
/** width of the labyrinth*/
private static int width;
/** 2-dimensionnal array representing the labyrinth
* map[i][j] is the j-th cell of the i-th column, it can be
* . : a hollow space
* # : a wall
* T : the starting position of kirk
* C : the control room
* ? : has not been scanned yet
*/
private static char map[][];
/** coordinates of Kirk*/
private static Coords c;
/** direction followed by kirk, which can be 1 of the 4 following constants*/
private static int direction;
private final static int UP = 0;
private final static int RIGHT = 1;
private final static int DOWN = 2;
private final static int LEFT = 3;
/** the 4 differents outputs possible*/
private static final String output[] = {"UP", "RIGHT", "DOWN", "LEFT"};
private static final Scanner in = new Scanner(System.in);
/** For code clarity, returns map[s.Y][s.X]*/
private static char map(Coords s) {
return map[s.Y][s.X];
}
/** For code clarity, returns true if and only if s is in the map*/
private static boolean isInMap(Coords s) {
return 0 <= s.X && s.X < width && 0 <= s.Y && s.Y < height;
}
/** Returns true if and only if map(s) is one of the chars of 'avoid'*/
private static boolean mustBeAvoided(Coords s, char[] avoid) {
for (char ch : avoid)
if (map(s) == ch)
return true;
return false;
}
/** Reads input for one game turn, updates kirk's coordinates,
* and the part of the map newly discovered*/
public static void readNewInfo() {
c.Y = in.nextInt();
c.X = in.nextInt();
for (int y = 0; y < height; y++) {
String ROW = in.next();
if (c.Y-2 <= y && y <= c.Y+2)
for (int x = Math.max(c.X-2, 0); x < Math.min(c.X+3, width); x++)
map[y][x] = ROW.charAt(x);
}
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
System.err.print(map[y][x]);
}
System.err.print("\n");
}
}
/** Computes the shortest path from Kirk to a cell containing char 'target',
* while avoiding characters contained by 'toAvoid'.
* If onlyReveal is true, walks this path until the target cell is revealed (ie != '?')
* Else, goes to the target cell.
* @return false if no cell containing char 'target' can be found, true else.*/
public static boolean goTo(char target, char[] toAvoid, boolean onlyReveal) {
// initializes an array to remember predecessors during BFS
int prec[][] = new int[height][width];
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++)
prec[y][x] = -1;
// initializes a queue to perform a BFS
LinkedList<Coords> queue = new LinkedList<Coords>();
queue.add(c);
// perform a BFS, avoid characters contained by 'toAvoid',
// until character 'target is found'
while(queue.size() > 0 && map(queue.element()) != target) {
Coords[] neighbours = queue.remove().neighbours();
for (int i = 0; i < neighbours.length; i++) {
Coords n = neighbours[i];
if (isInMap(n) && !mustBeAvoided(n, toAvoid) && prec[n.Y][n.X] == -1) {
prec[n.Y][n.X] = (i+2) % 4;
queue.add(n);
}
}
}
/* at this point, if queue is empty, no char 'target' is reachable
else, queue.element() is a target and path from Kirk to q.element() is generated
by reading precursors*/
if (queue.size() == 0)
return false;
else {
Coords targetCell = queue.remove();
Stack<Integer> path = new Stack<Integer>();
Coords iter = targetCell;
while (!iter.equals(c)) {
path.push((prec[iter.Y][iter.X]+2) % 4);
iter = iter.neighbours()[prec[iter.Y][iter.X]];
}
// If we just want to reveal the target, we stop when it is
// else we stop when Kirk is on it
while ((onlyReveal && map(targetCell) == target) ||
(!onlyReveal && !path.empty())) {
System.out.println(output[path.pop()]);
readNewInfo();
}
return true;
}
}
public static void main(String args[]) {
height = in.nextInt();
width = in.nextInt();
direction = UP;
c = new Coords(-1,-1);
int A = in.nextInt();
// Initializing the map
map = new char[height][width];
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++)
map[y][x] = '?';
readNewInfo();
// discovers the entire map
char[] avoidWallsAndControl = { '#', 'C' };
while (goTo('?', avoidWallsAndControl, true));
// goes to control room and goes back to start
char avoidWalls[] = { '#', '?' };
goTo('C', avoidWalls, false);
goTo('T', avoidWalls, false);
}
}
Erreurs fréquentes
- Déclencher l'alarme pendant l'explorationSi votre BFS d'exploration peut passer par C, Kirk risque de marcher dessus en se dirigeant vers une case inconnue, et le compte à rebours démarre avant que vous connaissiez un chemin de retour.
- Inverser lignes et colonnesL'arbitre envoie d'abord la ligne (KR), puis la colonne (KC). Les confondre ne se voit que sur les cartes non carrées, raison pour laquelle le premier test peut passer par chance.
- Vérifier seulement qu'un chemin de retour existeUn chemin de C vers T passant par des cases inexplorées peut ne pas exister, et le chemin connu peut être plus long que A. Assurez-vous que le chemin de retour n'utilise que des cases connues et qu'il est assez court avant d'entrer dans C.
- Relire l'entrée dans le mauvais ordreSi vous affichez un déplacement sans lire l'entrée du tour suivant (ou en la lisant deux fois), votre position se désynchronise de l'arbitre et tous les déplacements suivants sont faux.
Pour aller plus loin
Explorer tout le labyrinthe est la stratégie la plus simple, mais pas la plus économe en carburant. Une règle plus fine : dès que C est visible, BFS de C vers T sur les cases connues comme libres. Si cette distance est au plus A, on arrête d'explorer et on y va. Sinon on continue, mais en privilégiant les cases inconnues susceptibles de créer un raccourci entre C et T, comme les cases de frontière adjacentes aux deux régions. Sur les plus grandes cartes, l'exploration complète coûte des centaines de déplacements que cette sortie anticipée économise. Il y a aussi un piège subtil : le chemin vers C doit lui-même être calculé avec '?' bloqué, sinon Kirk peut tenter de traverser une case inconnue qui s'avère être un mur et perdre des tours à replanifier.
Questions fréquentes
Pourquoi un BFS plutôt qu'un DFS ou A* ?
Tous les déplacements coûtent 1, donc le BFS donne directement les plus courts chemins. A* n'aiderait que sur de très grandes grilles ouvertes, et le DFS produirait des parcours d'exploration longs et inefficaces.
La salle de contrôle peut-elle être inaccessible ?
Non, les tests contiennent toujours un C accessible et un chemin de retour dans le délai. Votre travail est de le découvrir sans déclencher l'alarme trop tôt.
Pourquoi Kirk oscille-t-il parfois entre deux cases ?
Cela arrive quand la cible est recalculée à chaque tour et que deux cases de frontière sont à égalité. S'engager sur une cible jusqu'à ce qu'elle soit révélée, comme le fait ce code, supprime l'oscillation.