Coding Solution

The Labyrinth – CodinGame solution in Java

HardBFSexplorationpathfindinggridUpdated
Short answer

Keep your own copy of the map, initially all '?', and update it from the 5x5 view each turn. First explore: repeatedly BFS to the nearest unknown cell while treating walls and the control room as blocked. Once nothing is left to discover, BFS to the control room, then BFS back to the start; with the whole map known, the return path is the shortest one and fits the alarm countdown.

The problem

Kirk is somewhere in a rectangular maze of R rows and C columns and can only see the cells within two squares of him. He must find the control room (C), step into it, and then get back to his starting point (T) before an alarm countdown of A turns runs out.

Every turn you get Kirk's row and column and the whole grid, where unseen cells are '?', walls '#' and open floor '.'. You answer UP, DOWN, LEFT or RIGHT. The jetpack only has fuel for a limited number of moves, so wandering aimlessly is not an option.

Approach, step by step

  1. Maintain a persistent mapStore every cell you have ever seen. The referee resends the grid each turn, but keeping your own copy lets you reason about the whole maze and print it to stderr for debugging.
  2. Explore with BFS to the nearest '?'Run a BFS from Kirk over known open cells, avoiding '#' and 'C', and stop at the first '?' dequeued. Walk along the path only until that cell becomes visible, then search again: this greedy frontier exploration wastes very few moves.
  3. Never step into C too earlyEntering the control room starts the alarm. Keeping 'C' in the blocked set during exploration guarantees the countdown only starts when you are ready.
  4. Go to the control roomWhen no reachable '?' remains, the map is fully known. BFS to 'C' through known cells (blocking '#' and '?') and follow the path.
  5. Return to the startBFS from C to T over the known map gives the shortest possible return path, which by construction of the tests fits within A moves. Follow it to win.

Complexity

TimeO(T · R · C)
SpaceO(R · C)

Each BFS is linear in the grid size, and the code runs at most one BFS per segment of movement, bounded by the T turns Kirk can play. Grids are at most 100x200, so this is well within limits.

Solution code

The Labyrinth – Java

goTo(target, toAvoid, onlyReveal) is a reusable BFS: with onlyReveal it walks until the target '?' is seen, otherwise until Kirk stands on it. The predecessor grid stores a direction index, so (dir + 2) % 4 gives the move to replay.

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);
    }
}
            

Common mistakes

Going further

Exploring the entire maze is the simplest strategy, but not the most economical in fuel. A sharper rule: as soon as C is visible, BFS from C to T over cells known to be open. If that distance is at most A, stop exploring and go. Otherwise keep exploring, but now prioritise unknown cells that could create a shortcut between C and T, such as frontier cells adjacent to both regions. On the largest maps, full exploration costs hundreds of moves that the early-exit rule saves. There is also a subtle trap: the path to C should itself be computed with '?' blocked, otherwise Kirk may try to walk through an unknown cell that turns out to be a wall and lose turns re-planning.

FAQ

Why BFS rather than DFS or A*?

All moves cost 1, so BFS gives shortest paths directly. A* would only help on very large open grids, and DFS would produce long, wasteful exploration routes.

Can the control room be unreachable?

No, the tests always contain a reachable C and a return path within the countdown. Your job is to discover it without starting the alarm early.

Why does Kirk sometimes oscillate between two cells?

That happens when the target is recomputed every turn and two frontier cells are tied. Committing to a target until it is revealed, as this code does, removes the oscillation.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome