소 발레

농부 존(Farmer John)의 자랑스러운 소 베시(Bessie)가 발레 입문 수업에 등록했다. FJ는 베시가 무대 가장자리에서 떨어지지 않고 춤 전체를 출 수 있을 만큼 충분히 큰 직사각형 무대를 만들고 싶어 한다.

베시의 춤은 1 x 1 정사각형 칸들의 격자로 이루어진 직사각형 무대에서 펼쳐진다. 베시의 네 발은 FR(오른쪽 앞발), FL(왼쪽 앞발), RR(오른쪽 뒷발), RL(왼쪽 뒷발)이다. 네 발은 정사각형을 이루는 인접한 4개의 칸에서 시작하며, 베시는 북쪽을 향하고 있다 (FL과 FR이 위 행에, RL과 RR이 그 아래에 있다).

베시의 춤은 N개 (1 <= N <= 1000)의 지시를 순서대로 따른다. 각 지시는 한 발을 한 칸 움직이거나 시계 방향으로 90도 회전하라는 것이다.

이동 지시는 3개의 문자로 이루어진다. 앞의 두 문자는 발(FR/FL/RR/RL)을 나타내고, 마지막 문자는 베시가 향한 방향을 기준으로 한 이동 방향(F = 앞, B = 뒤, R = 오른쪽, L = 왼쪽)을 나타낸다. 예를 들어 "FRF"는 오른쪽 앞발을 앞으로 한 칸 움직이라는 뜻이다.

회전 지시도 3개의 문자로 이루어진다. 앞의 두 문자는 베시가 바닥에 고정한 채 그 발을 중심으로 시계 방향으로 90도 회전하는 발 하나를 나타내고, 마지막 문자는 "P"이다. 예를 들어 "FRP"는 고정된 오른쪽 앞발을 중심으로 시계 방향으로 90도 회전하라는 뜻이다.

N개의 지시가 주어질 때, 춤 전체 동안 베시의 발을 모두 담을 수 있는 직사각형 무대의 최소 넓이를 계산하시오. 베시가 한 발을 다른 발이 있는 칸으로 옮기면 넘어진다. 이 경우 -1을 출력한다.

첫째 줄: 정수 N.

둘째 줄부터 1+N번째 줄까지: 각 줄에 베시의 춤에 포함된 3문자 지시 하나가 주어진다.

춤 전체 동안 베시의 발을 담는 데 필요한 직사각형 무대의 최소 넓이, 베시가 넘어지면 -1.

riseoj 작성

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