Farmer John's prize cow Bessie has signed up for an introductory ballet class, and FJ wants to build a rectangular stage large enough so that she can perform her entire dance without falling off the edges.

Bessie's dance takes place on a rectangular stage consisting of a grid of 1 x 1 square cells. Bessie's four feet are FR (front right), FL (front left), RR (rear right), RL (rear left). Her four feet start out in 4 adjacent cells forming a square, with Bessie facing north (FL and FR in the top row, RL and RR below them).

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.

A move instruction has 3 characters: the first two identify the foot (FR/FL/RR/RL), and the final character specifies the direction of movement (F = forward, B = back, R = right, L = left), relative to the direction Bessie is facing. For example, "FRF" means move the front right foot forward one cell.

A pivot instruction also has 3 characters: the first two specify the single foot Bessie keeps planted, around which she rotates 90 degrees clockwise, and the last character is "P". For example, "FRP" means pivot 90 degrees clockwise about the stationary front right foot.

Given the N instructions, please compute the minimum area of a rectangular stage necessary to contain her feet during the entire dance. If Bessie ever moves one foot onto the same cell as another foot, she trips; in that case output -1.

Line 1: The integer N.

Lines 2..1+N: Each line contains one of the 3-character instructions in Bessie's dance.

The minimum area of a rectangular stage necessary to contain Bessie's feet during the entire dance, or -1 if Bessie trips.

riseoj 작성

출처 올림피아드 > USACO > 2012-2013 > US Open > Bronze