Usaco_Contest_2013_Open_Bovine Problem 1. Bovine Ballet
Problem 1: Bovine Ballet [Brian Dean, 2013]
In an attempt to challenge the stereotypical perception of cows as awkward
creatures, Farmer John's prize cow Bessie has signed up for an introductory
ballet class. Her final performance is next week, and FJ wants to help her
by building a rectangular stage large enough so that she can perform her
entire dance without falling off the edges.
Bessie's dance will take place on a rectangular stage consisting of a grid
of 1 x 1 square cells. Bessie's four feet are described concisely as follows:
FR: Front right foot
FL: Front left foot
RR: Rear right foot
RL: Rear left foot
Her four feet start out in 4 adjacent cells forming a square as follows,
with Bessie facing north.
FL FR
RL RR
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.
Instructions to move a foot consist of 3 characters, the first two
identifying the foot to move, and the final character specifying the
direction of movement (F = forward, B = back, R = right, L = left). For
example, "FRF" means Bessie should move her front right foot forward one
cell, and "RLR" means she should move her rear left foot right one cell.
Of course, the direction of movement is relative to the direction Bessie is
facing.
Instruction to pivot are also 3 characters, the first two specifying the
single foot that Bessie keeps planted, around which she rotates 90 degrees
clockwise. The last character is "P" (for pivot). For example, the
instruction "FRP" means Bessie should pivot 90 degrees clockwise about her
stationary front right foot. This means that if her feet are currently
situated as follows (with Bessie facing north)
.. .. ..
.. .. FR
.. FL ..
.. RL RR
then the after the instruction "FRP" her feet will be located as follows,
with Bessie now facing east:
RL FL ..
RR .. FR
.. .. ..
.. .. ..
Given the N instructions in Bessie's dance, please compute the minimum area
of a rectangular stage necessary contain her feet during the entire dance.
If Bessie clumsily ever moves one foot onto the same cell as another foot,
she will trip and fail to complete the dance; in this case, please output
-1. Note that this is the only case where Bessie will trip; she has become
quite flexible after all her practice, and can easily move her feet into
rather strange configurations (for example, with her back feet farther
forward than her front feet).
PROBLEM NAME: ballet
INPUT FORMAT:
* Line 1: The integer N.
* Lines 2..1+N: Each line contains one of the 3-character instructions
in Bessie's dance.
SAMPLE INPUT (file ballet.in):
3
FRF
FRP
RLB
INPUT DETAILS:
Bessie's dance consists of the instructions "front right foot forward",
"front right foot pivot", and "rear left foot back".
OUTPUT FORMAT:
* Line 1: The minimum area of a rectangular stage necessary to contain
Bessie's feet during the entire dance, or -1 if Bessie trips.
SAMPLE OUTPUT (file ballet.out):
16
OUTPUT DETAILS:
Bessie needs a 4 x 4 stage to complete her dance. Her feet move as follows:
.. .. .. ..
.. .. .. .. (facing north)
.. .. FL FR
.. .. RL RR
After FRF:
.. .. .. ..
.. .. .. FR (facing north)
.. .. FL ..
.. .. RL RR
After FRP:
.. RL FL ..
.. RR .. FR (facing east)
.. .. .. ..
.. .. .. ..
After RLB:
RL .. FL ..
.. RR .. FR (facing east)
.. .. .. ..
.. .. .. ..
最新文章
- html5+jqueryMobile编写App推广注册页
- Integer与int的区别
- 从零开始山寨Caffe&#183;壹:仰望星空与脚踏实地
- Sublime Text 3 配置Java开发
- HDU 4045 Machine scheduling --第二类Strling数
- 循环语句for
- E:nth-child(n)实现奇偶匹配
- minicom/kermit捕捉日志
- 分割文件命令split
- .net entity framework 泛型 更新与增加记录
- 教程-Delphi设置功能表
- 那天有个小孩跟我说LINQ(三)转载
- IIS6、IIS7和IIS8各版本的差别
- IIS配置不正确可能导致“远程服务器返回错误: (404) 未找到";错误一例。
- NSURLConnection获取数据
- 一个好用的Dialog插件
- .Net开源oss项目进度更新(含小程序接口)
- C#中 Equals和= =的区别
- EntityFramework6.X之概述
- cs224d 自然语言处理作业 problem set3 (一) 实现Recursive Nerual Net Work 递归神经网络