AcWing 每日一题 2022/4/30【1959. 奶牛芭蕾】

为了挑战人们将奶牛视为笨拙生物的成见,农夫约翰的奶牛贝茜报名参加了芭蕾舞入门班。 她的最后一场演…

为了挑战人们将奶牛视为笨拙生物的成见,农夫约翰的奶牛贝茜报名参加了芭蕾舞入门班。

她的最后一场演出是下周,约翰想帮她搭建一个足够大的长方形舞台,这样她就可以在不从舞台边沿跌落的情况下表演整个舞蹈。

贝茜的舞蹈将在一个长方形的舞台上进行,这个舞台可以看作由 1×1 的单元格组成的矩阵。

贝茜的四只脚被简明扼要地描述如下:

她的四只脚最开始位于四个相邻的单元格中,这四个单元格可以构成一个小正方形,如下所示,贝茜朝北站立:

贝茜的舞蹈遵循一系列 N 条指令,每条指令要么指示她将一只脚移动一个单元格,要么指示她顺时针转动 90 度。

移动脚的指令由 3 个字符组成,前两个字符表明要移动的脚,最后一个字符指定移动方向(F = 前进,B = 后退,R = 右,L = 左)。

例如,FRF 表示贝茜应该将她的右前脚向前移动一个单元格,RLR 表示她应该将她的左后脚向右移动一个单元格。

当然,运动的方向与贝茜面对的方向是相对的。

贝茜的顺时针转动是以某一只脚作为枢轴而进行的,转动时枢轴脚应保持竖立,并围绕该脚进行顺时针转动。

顺时针转动的指令也由 3 个字符组成,前两个字符表明枢轴脚,最后一个字符为 P,表示该脚作为枢轴。

例如,FRP 表示贝茜应该以右前脚作为枢轴,围绕其顺时针旋转 90 度。

这意味着,如果贝茜的脚现在处于如下位置(贝茜朝北站立):

执行完 FRP 指令以后,她的脚将位于如下位置,贝茜现在朝东站立:

给定贝茜舞蹈的 N 条指令,请计算能够使贝茜全程不踩空跌落的长方形舞台的最小面积。

如果贝茜将一只脚移动到与另一只脚相同的单元格内,她就会被绊倒,从而无法完成舞蹈。

这种情况下,请输出 −1。

注意,这是贝茜唯一能够被绊倒的情况,在经过所有练习以后,贝茜十分灵活,很容易摆出各种高难度姿势(例如,后脚比前脚更向前)。

输入格式
第一行包含整数 N。

接下来 N 行,每行包含三个字符,表示一个舞蹈指令。

输出格式
输出在整个舞蹈过程中,能够容纳贝茜的脚所必须的长方形舞台的最小面积。

如果贝茜被绊倒,则输出 −1。

数据范围

1≤N≤1000

输入样例:

输出样例:

样例解释
贝茜需要一个 4×4 大小的舞台,保证她能够完成她的舞蹈。

她的脚步如下:

执行 FRF 后:

执行 FRP 后:

执行 RLB 后:

题目分析

题目主要的两个难点在旋转后的坐标该如何确定,以及旋转后的方向,方向决定了奶牛,前后左右的方向(这一点非常重要)
需要推一下公式,(x1, y1) 绕定点 (x2, y2) 顺时针旋转至 (x3, y3) 公式如下:
x3 = x1 – y2 + x2;
y3 = x2 + y2 – x1;
旋转之后方向也随之发生改变,方向的改变影响的是前后左右的移动,而不影响旋转,因此方向改变,我们就只需要改变对应的前后左右移动的偏移量就可以了

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/4264.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部