import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; /* In this problem, which was inspired by a computer game from 90's, your * goal is to help the heretic (the main character of the game) get out * of the maze. Different locations of the maze are separated by locked * doors which can be opened only by a key of the right color. You must * navigate the heretic through the maze, such that he finds all the * necessary keys to open the doors blocking the way towards the exit, * and moreover, do that in the shortest number of steps possible. * * The maze is build out of walls ('#'), corridors (' '), doors ('R', 'G', 'B') * and exit ('E'). You may assume the maze is enclosed by walls (including 'E'). * In the maze you can find the heretic ('H') and keys associated with the doors * ('r', 'g', 'b'). * * Output should be a set of instructions in the form of upper-case letters * denoting the directions ('L', 'R', 'U', 'D') in which the heretic has to * move from his initial position to reach the exit in the shortest number * of steps. Or say, there is no way out! */ public class heretic { /* The directions in which the heretic can move. */ public static final int[][] DIRECTIONS = new int[][]{{-1, 0},{1, 0},{0, -1},{0, 1}}; /* The representation of a state of the world. */ public static class QueueState { public int keys; // A bitmask encoding the possession of keys. public int x; // Heretic's x position in the world. public int y; // Heretic's y position in the world. public int elapsed; // The time it took to get into this state. /* Returns a unique identifier for this state of the world. The size * of the input allows to have a global arrays (``predecessor``, ``time``, * ``resolved``) which elements are associated with individual states * of the world, in general case, we would need to replace those arrays * with hash maps. */ public int getId() { return (this.keys << 10) + (this.x << 5) + this.y; } /* Returns ``true`` only if the heretic in this state possess * the specified key. */ public boolean hasKey(int key) { return (this.keys & key) != 0; } /* Sets the indicator of possession of the specified key * for this state to ``true``. */ public void foundKey(int key) { this.keys |= key; } /* Returns a new state which was created from this state * by moving the heretic in the specified direction. */ public QueueState move(int[] direction) { QueueState copy = new QueueState(); copy.keys = this.keys; copy.x = this.x + direction[0]; copy.y = this.y + direction[1]; copy.elapsed = this.elapsed; return copy; } } public static final int RED_KEY = 1; public static final int GREEN_KEY = 2; public static final int BLUE_KEY = 4; public static final int MAX_MAP_WIDTH = 32; public static final int MAX_MAP_HEIGHT = 32; /* The size of the input was chosen to accomodate everyting within arrays. */ public static final int MAXSTATES = 8 * MAX_MAP_WIDTH * MAX_MAP_HEIGHT; /* Stores the map read from the input. */ public static char[][] map = new char[MAX_MAP_HEIGHT][MAX_MAP_WIDTH]; /* Keeps track how we got to each (reachable) state. */ public static QueueState[] predecessor = new QueueState[MAXSTATES]; /* Keeps track of how long it took to get into the state (situation). */ public static int[] time = new int[MAXSTATES]; /* Indicates whether we have found the state (situation) in the smallest possible time. */ public static boolean[] resolved = new boolean[MAXSTATES]; /* Compares the states (situations) by the time it took to get into them. */ public static Comparator stateComparator = new Comparator() { public int compare(QueueState one, QueueState two) { return one.elapsed - two.elapsed; } }; /* The only needed sophisticated data structure we would not like to code by ourselves. */ public static PriorityQueue queue = new PriorityQueue(stateComparator); /* Returns ``true`` only if the state is valid to expand the search into. */ public static boolean isValid(QueueState state) { /* There is no restriction on the state. We do not want to expend states * which have been already solved. */ return !resolved[state.getId()]; } /* Try to put ``nextState`` state in the queue. */ public static void tryEnqueueState(QueueState nextState, QueueState prevState, Integer moveTime) { /* If the next state has not been already resolved and we can improve * on the time we get to it -- we add it into the queue. */ if (isValid(nextState) && time[prevState.getId()] + moveTime < time[nextState.getId()]) { nextState.elapsed = time[nextState.getId()] = time[prevState.getId()] + moveTime; queue.add(nextState); /* Remember how we got there. */ predecessor[nextState.getId()] = prevState; } } /* Move the heretic from his current position in all directions and try * to put the resulting state into the queue. */ public static void expandState(QueueState state) { for (int[] direction : DIRECTIONS) { QueueState nextState = state.move(direction); if (map[nextState.y][nextState.x] != '#') { switch (map[nextState.y][nextState.x]) { case 'r': nextState.foundKey(RED_KEY); tryEnqueueState(nextState, state, 1); break; case 'R': if (nextState.hasKey(RED_KEY)) tryEnqueueState(nextState, state, 1); break; case 'g': nextState.foundKey(GREEN_KEY); tryEnqueueState(nextState, state, 1); break; case 'G': if (nextState.hasKey(GREEN_KEY)) tryEnqueueState(nextState, state, 1); break; case 'b': nextState.foundKey(BLUE_KEY); tryEnqueueState(nextState, state, 1); break; case 'B': if (nextState.hasKey(BLUE_KEY)) tryEnqueueState(nextState, state, 1); break; default: tryEnqueueState(nextState, state, 1); break; } } } } /* Read the map from the standard input and return the state associated * with the initial position of the heretic. */ public static QueueState readMap(BufferedReader reader) throws IOException { String line = null; QueueState start = new QueueState(); int iRow = 0; while ((line = reader.readLine()) != null) { int iCol = 0; for (int i = 0; i < line.length(); i++) { map[iRow][iCol] = line.charAt(i); if (map[iRow][iCol] == 'H') { start.x = iCol; start.y = iRow; } ++iCol; } ++iRow; } return start; } /* Retrieve the instruction to move from the specified states * which follows each other in the sequence. */ public static final char getMove(QueueState state, QueueState nextState) { if (state.x - nextState.x != 0) return (state.x - nextState.x < 0) ? 'L' : 'R'; if (state.y - nextState.y != 0) return (state.y - nextState.y < 0) ? 'D' : 'U'; return '?'; } /* Returns ``true`` only if the heretic stands on the exit from the maze. */ public static final boolean isFinalState(QueueState state) { return (map[state.y][state.x] == 'E'); } public static void main(String[] arguments) throws IOException { Arrays.fill(time, Integer.MAX_VALUE); /* Read the map from the standard input and get the initial state. */ QueueState state = readMap(new BufferedReader(new InputStreamReader(System.in))); /* Add the initial state into the queue. */ queue.add(state); time[state.getId()] = 0; /* Until the queue get emptied or a solution has been found. */ while ((state = queue.poll()) != null && !isFinalState(state)) { if (!resolved[state.getId()]) { resolved[state.getId()] = true; expandState(state); } } /* Print out the instructuons or prompt there is no way out. */ if (state == null) { System.out.println("There is no way out, arrrgh!"); } else { String solution = ""; while (predecessor[state.getId()] != null) { solution = getMove(predecessor[state.getId()], state) + solution; state = predecessor[state.getId()]; } System.out.println(solution); } } }