#P2206. 奶牛芭蕾

奶牛芭蕾

题目描述

她的期末汇报演出就在下周,于是Farmer Jhon 就帮她建一个长方形的舞台。

为了防止Bessie从舞台边缘掉下,FJ决定要建一个足够大的舞台。

Bessie的舞蹈将会占用一个由许多1 x 1的正方形方块组成的长方形的区域。为了方便,我们把Bessie的四只脚按如下方式简写:

FR : 前右脚(Front right foot)

FL :前左脚(Front left foot)

RR :后右脚(Rear right foot)

RL :后左脚(Rear left foot)

Bessie将会从一个如下的四个相邻的格子出发,同时她会面向北方。

FL FR

RL RR

Bessie的舞蹈会依据总数为N(1 <= N <= 1000 ) 的指令进行。每一条指令都指示Bessie将一只脚移动一个格子,或者顺时针旋转90°

其中,移动的指示由三个字符组成,其中前两个是脚的代号,最后一个代表脚移动的方向("F" - 向前 "B" - 向后 "R" - 向右 "L" - 向左)

比如说, "FRF"代表着Bessie的前右脚向前移动一个格子,"RLR"代表她的后左脚将向右移一个格子

当然,我们这里说的方向是以Bessie正面对的方向决定的。

另一方面,旋转的指令也是3个字符,其中前两个字母也是脚的代号,代表着旋转的支点。最后一个字母总是为"P"(pivot)。

比如说, "FRP"代表着Bessie将以前右脚为支点,顺时针旋转90°。

如果我们从图中看,假设现在Bessie的脚是这样的,她正朝向北方。

.. .. ..

.. .. FR

.. FL ..

.. RL RR

那么在进行指令"FRP"之后,她的脚的位置将变成下面这样,同时她将会朝向左边:

RL FL ..

RR .. FR

.. .. ..

.. .. ..

现在已知N条Bessie的舞蹈的指令,请你计算她的整个舞蹈所需要的最小的长方形舞台,使得Bessie的脚不会落到舞台之外。

如果无论怎么样,她都会使自己的两个脚移动到相同的格子里,那么她就会被绊倒,并搞砸这次表演。

在这样的情况下,请输出-1。

不过这是Bessie会被绊倒的唯一的原因,因为她在经过练习之后,身体十分的柔软,可以轻松的做到任何奇怪的动作(比如说把后脚伸到前脚的前面)

(吐槽:那你就不能两只脚放在一起?)

(吐槽2:如果你觉得里面的配图有点怪异的话,就把它复制到记事本 ,把字体改成Courier New即可)

输入格式

第一行是整数N ( 1 <= N <= 1000)

第二至N+1行是如题所述的指令,每行有三个字符

输出格式

一行,输出舞台的最小面积

3
FRF
FRP
RLB
16

提示

样例的输出解释:

Bessie的舞蹈需要至少4 x 4的舞台,并将会按下图进行:

.. .. .. ..

.. .. .. .. (朝向北)

.. .. FL FR

.. .. RL RR

FRF之后:

.. .. .. ..

.. .. .. FR (朝向北)

.. .. FL ..

.. .. RL RR

FRP之后:

.. RL FL ..

.. RR .. FR (朝向东)

.. .. .. ..

.. .. .. ..

RLB之后:

RL .. FL ..

.. RR .. FR (朝向西)

.. .. .. ..

.. .. .. ..