Problem D
The Labyrinth

Your friend has recently started playing the hit game Labyrinths and Lizards. The game involves entering a labyrinth where you must fight enemies to eventually reach the boss (the toughest enemy). You can’t see the entire labyrinth when you enter; you have to explore it to find the boss. Unfortunately, not all paths lead directly to the boss—many lead to dead ends. To play the game optimally, it’s crucial to use all available information to reach the boss as quickly as possible.

Speed is so important that players have gathered a large number of labyrinth layouts. Some players have spent hours practicing these layouts to get better at guessing the path. You immediately think this is extremely inefficient: even if you don’t know exactly how the labyrinths are generated, you should have enough examples to write a program that is better than humans.

A labyrinth is shaped like a $9 \times 9$ grid and can look like this:

There are 4 special types of rooms:

• S: This is the room where you start in the labyrinth.

• B: This room contains the boss. The goal is to reach this room as quickly as possible.

• T: This room contains a hidden treasure. However, you are not interested in it.

• L: These 5 rooms each contain a lever. If you enter the room and pull the lever, the treasure is unlocked, and you learn the location of the treasure room. Note that you can enter the treasure room even if you haven’t pulled the lever, and since you don’t care about the treasure, the only thing you gain from pulling the lever is information.

There is exactly 1 room each of type S, B, and T, and 5 rooms of type L.

In one move, you can go to one of the adjacent rooms. Your task is to write a program that reaches the boss. You get more points the fewer moves you make. When the program starts and after each move, you receive the following information:

• The directions (up, down, left, right) you can move.

• The type of room you are currently in (S, B, T, L, or E). E means the room is not special.

• Your current position.

• The location of the treasure room (if you have pulled a lever).

The grid’s rows and columns are numbered as follows:

Interaction

When your program starts and after each move, it should read a line in the following format:
LURD K $\, p_r$ $\, p_c$ $\, t_r$ $\, t_c$

With the following meanings:

• L,U,R,D are all 0 or 1.

• If L is 1, you can move left, otherwise you cannot.

• If U is 1, you can move up, otherwise you cannot.

• If R is 1, you can move right, otherwise you cannot.

• If D is 1, you can move down, otherwise you cannot.

• K describes the type of room you are currently in. This will always be one of S, B, T, L, or E, as described above.

• $p_r$ is the row you are currently in.

• $p_c$ is the column you are currently in.

• $t_r$ is the row where the treasure room is located. If you haven’t pulled a lever yet, this will be -1.

• $t_c$ is the column where the treasure room is located. If you haven’t pulled a lever yet, this will be -1.

To make a move, print a letter indicating the direction you want to go in: < (left), > (right), V (down), or ^ (up). Then read the information again, make another move, and so on until you reach the boss.

If you ever read that K is B, meaning you are at the boss, your program should terminate. If you don’t, you might get strange errors.

If you ever enter a room with a lever, you will automatically pull it.

If you try to move in a direction you cannot, you will receive Wrong Answer.

Make sure to flush the output after each move, otherwise, you may receive Time Limit Exceeded. In C++, this can be done with cout << flush or fflush(stdout); in Python with stdout.flush(); and in Java with System.out.flush().

Scoring

Your solution will be tested on multiple test cases. Let ”moves” be the number of moves you make to reach the boss. The score for a given test case is calculated using the following formula:

• If $\text{moves} \leq 24$, you get $\min (100, 170-7 \cdot \text{moves})$ points.

• Otherwise, if $\text{moves} \leq 1000$, you get 1 point.

• Otherwise, you get 0 points.

Your total score is the average score across all test cases.

During the competition, you will be tested on exactly 30 test cases. After the competition, your solution will be rerun with 70 other test cases. It is guaranteed that the 70 cases at the end of the competition are comparable to the 100 cases used during the competition.

Downloads

At the bottom of the homepage, you can download labyrinth.zip. This contains 10000 test cases generated in the same way as the data used on Kattis. It also includes other helpful programs.

Example

Below is an interaction between the judge and a program solving the example case illustrated by the image above.

0101 S 3 3 -1 -1

^

0011 E 2 3 -1 -1

>

1100 E 2 4 -1 -1

^

0001 L 1 4 2 2

V

1100 E 2 4 2 2

<

0011 E 2 3 2 2

V

0101 S 3 3 2 2

V

1110 E 4 3 2 2

>

1101 E 4 4 2 2

V

0101 E 5 4 2 2

V

1100 E 6 4 2 2

<

1111 E 6 3 2 2

V

1110 E 7 3 2 2

>

1010 E 7 4 2 2

>

1010 E 7 5 2 2

>

1100 E 7 6 2 2

^

0001 B 6 6 2 2