The Labyrinth – CodinGame solution in Java
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
- 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.
- 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.
- 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.
- 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.
- 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
O(T · R · C)O(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
- Triggering the alarm while exploringIf your exploration BFS can route through C, Kirk may step on it while heading for an unknown cell, and the countdown starts before you know a way back.
- Swapping rows and columnsThe referee sends the row (KR) first, then the column (KC). Mixing them up only shows on non-square maps, which is why the first test can pass by luck.
- Only checking that a path back existsA path from C to T that goes through unexplored cells may not exist, and the known path may be longer than A. Make sure the return path uses only known cells and is short enough before entering C.
- Re-reading input in the wrong orderIf you print a move without reading the next turn's input (or read twice), your position goes out of sync with the referee and every following move is wrong.
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.