Coding Solution

The Labyrinth – solution CodinGame en Java

DifficileBFSexplorationpathfindinggridMis à jour le
Réponse courte

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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é

TempsO(T · R · C)
MémoireO(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

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.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome