Problem 1: Bovine Ballet [Brian Dean, 2013]

In an attempt to challenge the stereotypical perception of cows as awkward

creatures, Farmer John's prize cow Bessie has signed up for an introductory

ballet class. Her final performance is next week, and FJ wants to help her

by building a rectangular stage large enough so that she can perform her

entire dance without falling off the edges.

Bessie's dance will take place on a rectangular stage consisting of a grid

of 1 x 1 square cells. Bessie's four feet are described concisely as follows:

FR: Front right foot

FL: Front left foot

RR: Rear right foot

RL: Rear left foot

Her four feet start out in 4 adjacent cells forming a square as follows,

with Bessie facing north.

FL FR

RL RR

Bessie's dance follows a series of N instructions (1 <= N <= 1000), where

each instruction tells her to either move one foot by one cell or to pivot

90 degrees clockwise.

Instructions to move a foot consist of 3 characters, the first two

identifying the foot to move, and the final character specifying the

direction of movement (F = forward, B = back, R = right, L = left). For

example, "FRF" means Bessie should move her front right foot forward one

cell, and "RLR" means she should move her rear left foot right one cell.

Of course, the direction of movement is relative to the direction Bessie is

facing.

Instruction to pivot are also 3 characters, the first two specifying the

single foot that Bessie keeps planted, around which she rotates 90 degrees

clockwise. The last character is "P" (for pivot). For example, the

instruction "FRP" means Bessie should pivot 90 degrees clockwise about her

stationary front right foot. This means that if her feet are currently

situated as follows (with Bessie facing north)

.. .. ..

.. .. FR

.. FL ..

.. RL RR

then the after the instruction "FRP" her feet will be located as follows,

with Bessie now facing east:

RL FL ..

RR .. FR

.. .. ..

.. .. ..

Given the N instructions in Bessie's dance, please compute the minimum area

of a rectangular stage necessary contain her feet during the entire dance.

If Bessie clumsily ever moves one foot onto the same cell as another foot,

she will trip and fail to complete the dance; in this case, please output

-1. Note that this is the only case where Bessie will trip; she has become

quite flexible after all her practice, and can easily move her feet into

rather strange configurations (for example, with her back feet farther

forward than her front feet).

PROBLEM NAME: ballet

INPUT FORMAT:

* Line 1: The integer N.

* Lines 2..1+N: Each line contains one of the 3-character instructions

in Bessie's dance.

SAMPLE INPUT (file ballet.in):

3

FRF

FRP

RLB

INPUT DETAILS:

Bessie's dance consists of the instructions "front right foot forward",

"front right foot pivot", and "rear left foot back".

OUTPUT FORMAT:

* Line 1: The minimum area of a rectangular stage necessary to contain

Bessie's feet during the entire dance, or -1 if Bessie trips.

SAMPLE OUTPUT (file ballet.out):

16

OUTPUT DETAILS:

Bessie needs a 4 x 4 stage to complete her dance. Her feet move as follows:

.. .. .. ..

.. .. .. .. (facing north)

.. .. FL FR

.. .. RL RR

After FRF:

.. .. .. ..

.. .. .. FR (facing north)

.. .. FL ..

.. .. RL RR

After FRP:

.. RL FL ..

.. RR .. FR (facing east)

.. .. .. ..

.. .. .. ..

After RLB:

RL .. FL ..

.. RR .. FR (facing east)

.. .. .. ..

.. .. .. ..