P2206 [USACO13OPEN] Bovine Ballet B

Bessie has become a ballet dancer.

Her final recital is next week, so Farmer John (FJ) builds her a rectangular stage. To keep Bessie from falling off the edge, FJ decides to build a stage that is large enough. Bessie's dance will occupy a rectangular region composed of many $1 \times 1$ square cells. For convenience, we abbreviate Bessie's four hooves as follows: - `FR`: front right hoof (Front right hoof) - `FL`: front left hoof (Front left hoof) - `RR`: rear right hoof (Rear right hoof) - `RL`: rear left hoof (Rear left hoof) Bessie starts with her hooves occupying four adjacent cells as shown below, initially facing north. ```plain FL FR RL RR ``` Bessie's dance consists of $N\ (1 \le N \le 1000)$ instructions. Each instruction either moves one hoof by one cell or rotates $90^\circ$ clockwise. A move instruction has three characters, where the first two are the hoof code, and the last character is the direction of movement: - `F`: forward - `B`: backward - `R`: right - `L`: left For example, `FRF` means Bessie's front right hoof moves forward by one cell, and `RLR` means her rear left hoof moves right by one cell. Directions are relative to the direction Bessie is currently facing. Rotation instructions also have $3$ characters. The first two letters are the hoof code and denote the pivot. The last letter is always `P` (pivot). For example, `FRP` means Bessie rotates $90^\circ$ clockwise about her front right hoof. From the diagram, suppose Bessie's hooves are positioned as follows while she is facing north: ```plain .. .. .. .. .. FR .. FL .. .. RL RR ``` After executing the instruction `FRP`, her hooves become: ```plain RL FL .. RR .. FR .. .. .. .. .. .. ``` and she will be facing east. Given $N$ dance instructions, compute the minimal rectangular stage area required so that Bessie's hooves never step outside the stage throughout the dance. If at any time two of her hooves occupy the same cell, she will trip and ruin the performance. In this case, output $-1$. However, this is the only reason Bessie would trip, since after practice she is very flexible and can easily perform any unusual moves (for example, extending a hind hoof ahead of a front hoof).

The first line contains an integer $N$. Each of the next $N$ lines contains $3$ uppercase letters describing an instruction.

Output a single line with the minimal stage area.

Sample explanation: Bessie's dance requires at least a $4 \times 4$ stage and proceeds as shown: ```plain .. .. .. .. .. .. .. .. .. .. FL FR .. .. RL RR [Face north] ``` After `FRF`: ```plain .. .. .. .. .. .. .. FR .. .. FL .. .. .. RL RR [Face north] ``` After `FRP`: ```plain .. RL FL .. .. RR .. FR .. .. .. .. .. .. .. .. [Face east] ``` After `RLB`: ```plain RL .. FL .. .. RR .. FR .. .. .. .. .. .. .. .. [Face west] ``` Translated by ChatGPT 5