#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 (朝向西)
.. .. .. ..
.. .. .. ..