Problem E
Turtle Master
Robot Turtles is one of Theta’s favorite games. In this game, kindergarteners learn how to “code” by creating programs that move a turtle from a starting field to a diamond. Robot Turtles is reportedly the most successful game funded by the Kickstarter incubator.
In the actual board game, an adult plays the role of the “turtle master,” which is the person that plays the role of a CPU to execute the program. As you can imagine, this is a pretty boring task that cries out for automation: in this problem, you are asked to write a program that automates the task of the turtle master.
Robot Turtles is played on an $8 \times 8$ board. There is one turtle (marked with the letter T), which always starts out at the bottom-left field, facing right. The board contains empty squares (marked as .), castles made out of rock (C), and castles made out of ice (I). The diamond is marked with a D. The turtle may move only onto empty squares and the square on which the diamond is located.
A turtle program contains $4$ kinds of instructions, marked by a single letter.
-
F The turtle moves one field forward in the direction it is facing. If the turtle faces a castle or the border of the board, a program error occurs.
-
R The turtle turns $90$ degrees to the right (the turtle will just turn and stay on the same field).
-
L The turtle turns $90$ degrees to the left (the turtle will just turn and stay on the same field).
-
X The turtle fires a laser in the direction it is facing. If the square it is facing contains an ice castle, the ice castle will melt and the square will turn into an empty square. Otherwise, a program error occurs. The turtle will not move or change direction. It is a program error to fire the laser at empty squares, rock castles or outside the board.
Input
The input consists of $9$ lines. The first $8$ lines contains the board, each line representing the squares in a row of the board. The turtle will always be at the bottom-left. There will be exactly $1$ diamond. The $9^{\text {th}}$ line contains the program the turtle master is asked to execute, which contains at least $1$ and at most $60$ instructions.
Output
Output Diamond! if the entire program can be executed without program error and if the turtle is on the diamond square after the program has been executed. Output Bug! if a program error occurred, or if the turtle does not end up on the diamond square!
| Sample Input 1 | Sample Output 1 |
|---|---|
........ ........ ........ ...CC... ..C.DC.. .C..C... C.IC.... T.C..... FLFRXFLFRFLFRF |
Diamond! |
| Sample Input 2 | Sample Output 2 |
|---|---|
........ ........ ........ ...CC... ..C.DC.. .C..C... C.IC.... T.C..... FLFRFLFRFLFRF |
Bug! |
| Sample Input 3 | Sample Output 3 |
|---|---|
........ ........ ........ ...CC... ..C.DC.. .C..C... C.IC.... T.C..... FLFRXFLFRFLFFR |
Bug! |
