Snake game simulation

Time limit1sMemory limit256 MB

Summary

Simulate 20 snake moves on a 15 by 15 board with growth on pellets and print the pellet count or game over with the final board.

Level: Easy3 of 10
Topics: Simulation, Queue
Solved: No attempts yet

Problem

Simulate the snake game that came with old Nokia phones.

The board is a $15 \times 15$ grid. Every cell holds a space, the letter X, or the letter F. X is the snake's body. When a game starts the snake is exactly three X cells side by side in one row. The rightmost of the three is the head, and the snake moves to the right. F is a food pellet. The snake eats pellets and grows without leaving the board and without running into itself.

One data set is a string of 20 characters made only of U, D, L, R and O. U turns the snake up, D down, L left, R right, and O keeps the current direction. Each character is one move.

A move is resolved in this order.

The target cell is the cell next to the head in the current direction.
If the target cell is on the board and holds a pellet, the snake grows by one cell and the tail stays where it is. Otherwise the tail cell is removed from the snake.
If the target cell is off the board, or the target cell is still occupied by the snake after the tail was removed, the game ends.
Otherwise the head moves onto the target cell. If a pellet was there, the pellet is removed and the number eaten goes up by one.

Once a game ends, the remaining characters of that data set are not processed.

Every data set starts again from the board given in the input.

Input

The first 15 lines are the $15 \times 15$ grid. Each line has 15 characters, and trailing spaces may be missing. Exactly three cells hold X, and they are side by side in one row.

The next line has the number of data sets $T$ . $T$ is at least 1.

Each of the next $T$ lines has a string of 20 characters made only of U, D, L, R and O.

Output

For each data set print one line. Print GAME OVER if the game ended, otherwise print the number of pellets eaten, one space, and pellets. Write pellets even when the number is 1.

Then print the final board on 15 lines. A cell the snake occupies is X, a remaining pellet is F, and every other cell is a space. If the game ended because the snake left the board, the head is off the board and is not drawn.

Print a blank line between data sets.

Examples2

Example 1

Input

F             F
        F    F 
 F             
 F             
               
  F     F      
               
               
               
  XXX    F     
               
               
      F  F     
               
              F
2
UROOOUOOLOOOOOOUOOOO
UOOOOOOOOOOOOOOOOOOO

Expected output

4 pellets
FX            F
 X      F    F 
 X             
 X             
 X             
 XX            
               
               
               
         F     
               
               
      F  F     
               
              F

GAME OVER
F   X         F
    X   F    F 
 F             
 F             
               
  F     F      
               
               
               
         F     
               
               
      F  F     
               
              F

Example 2

Input

F              
               
               
               
               
               
               
     XXX       
               
               
               
               
               
               
              F
1
DDDDLLLLUUUURRRROOOO

Expected output