USACO 2013 US Open Bronze 奶牛芭蕾 (图形学 矩阵坐标变换)

2023-11-06 16:40

本文主要是介绍USACO 2013 US Open Bronze 奶牛芭蕾 (图形学 矩阵坐标变换),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

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

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

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

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

FR:右前脚
FL:左前脚
RR:右后脚
RL:左后脚

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

FL FR
RL RR

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

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

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

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

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

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

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

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

.. .. .. 
.. .. FR 
.. FL .. 
.. RL RR 

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

RL FL .. 
RR .. FR 
.. .. ..  
.. .. .. 

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

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

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

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

输入格式

第一行包含整数 N。

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

输出格式

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

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

数据范围
1 ≤ N ≤ 1000 1≤N≤1000 1N1000

输入样例:

3
FRF
FRP
RLB

输出样例:

16
样例解释

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

她的脚步如下:

.. .. .. .. 
.. .. .. .. (朝北)
.. .. FL FR 
.. .. RL RR 

执行 FRF 后:

.. .. .. .. 
.. .. .. FR (朝北)
.. .. FL .. 
.. .. RL RR 

执行 FRP 后:

.. RL FL .. 
.. RR .. FR (朝东)
.. .. .. .. 
.. .. .. .. 

执行 RLB 后:

RL .. FL ..
.. RR .. FR (朝东)
.. .. .. ..
.. .. .. ..

分析

本题目的关键问题在于矩阵顺时针旋转时的坐标变换
[ X n e w Y n e w ] = [ X o l d Y o l d ] [ c o s θ − s i n θ s i n θ c o s θ ] \begin{bmatrix} X_{new} Y_{new}\\ \end{bmatrix} = \begin{bmatrix} X_{old} Y_{old}\\ \end{bmatrix} \begin{bmatrix} cosθ & -sinθ \\ sinθ & cosθ \end{bmatrix} [XnewYnew]=[XoldYold][cosθsinθsinθcosθ]
由于本题目是旋转90°,所以把θ=90带入得到:
[ X n e w Y n e w ] = [ X o l d Y o l d ] [ c o s 90 − s i n 90 s i n 90 c o s 90 ] = [ X o l d Y o l d ] [ 0 − 1 1 0 ] = [ Y o l d − X o l d ] \begin{bmatrix} X_{new} Y_{new}\\ \end{bmatrix} = \begin{bmatrix} X_{old} Y_{old}\\ \end{bmatrix} \begin{bmatrix} cos90 & -sin90 \\ sin90 & cos90 \end{bmatrix} = \begin{bmatrix} X_{old} Y_{old}\\ \end{bmatrix} \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} Y_{old} -X_{old} \end{bmatrix} [XnewYnew]=[XoldYold][cos90sin90sin90cos90]=[XoldYold][0110]=[YoldXold]

每次旋转过后方向都会改变,我们默认朝前为0。
在这里插入图片描述

刚开始的四个脚的方位

在这里插入图片描述

C++ 代码

#include<bits/stdc++.h>#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;//定义初始四个坐标
PII p[4] = {{0, 1}, {1, 1}, {0, 0}, {1, 0}};
//定义刚开始的四个脚的方位
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
unordered_map<string, int> id = {{"FL", 0}, {"FR", 1}, {"RL", 2}, {"RR", 3}};
//定义转向的坐标
unordered_map<char, int> turn = {{'F', 0}, {'B', 2}, {'L', 3}, {'R', 1}};
int minx = 0, maxx = 1, miny = 0, maxy = 1;//旋转函数 b相对a转
void rotate(PII& a, PII& b)
{//计算该向亮b.x -= a.x, b.y -= a.y;//由于是顺时针旋转90度,就把坐标带入进行计算int x = b.y, y = -b.x;//新的坐标加等于旧的坐标加上偏移量b.x = a.x + x, b.y = a.y + y;
}int main()
{int n;cin >> n;int d = 0;while (n -- ){string str;cin >> str;int k = id[str.substr(0, 2)];char c = str[2];if (c != 'P'){int t = (d + turn[c]) % 4;p[k].x += dx[t], p[k].y += dy[t];}else{for (int i = 0; i < 4; i ++ ){if (i != k)rotate(p[k], p[i]);                }//旋转后方向改变d = (d + 1) % 4;}//检查是否两只脚会踩在同一块地板上,如果有直接输出-1for (int i = 0; i < 4; i ++ )for (int j = 0; j < i; j ++ )if (p[i] == p[j]){puts("-1");return 0;}for (int i = 0; i < 4; i ++ ){// 求出这个过程中最小最大的四个边界minx = min(minx, p[i].x);miny = min(miny, p[i].y);maxx = max(maxx, p[i].x);maxy = max(maxy, p[i].y);}}cout << (maxx - minx + 1) * (maxy - miny + 1) << endl;return 0;
}

这篇关于USACO 2013 US Open Bronze 奶牛芭蕾 (图形学 矩阵坐标变换)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/357818

相关文章

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

usaco 1.3 Calf Flac(暴搜)

思路是暴搜。 需要注意的地方是输入的方法,以及输出时的换行。 代码: /*ID: who jayLANG: C++TASK: calfflac*/#include<stdio.h>#include<string.h>#include<math.h>int main(){freopen("calfflac.in","r",stdin);freopen("calfflac.ou

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

usaco 1.2 Palindromic Squares(进制转化)

考察进制转化 注意一些细节就可以了 直接上代码: /*ID: who jayLANG: C++TASK: palsquare*/#include<stdio.h>int x[20],xlen,y[20],ylen,B;void change(int n){int m;m=n;xlen=0;while(m){x[++xlen]=m%B;m/=B;}m=n*n;ylen=0;whi

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

usaco 1.2 Milking Cows(类hash表)

第一种思路被卡了时间 到第二种思路的时候就觉得第一种思路太坑爹了 代码又长又臭还超时!! 第一种思路:我不知道为什么最后一组数据会被卡 超时超了0.2s左右 大概想法是 快排加一个遍历 先将开始时间按升序排好 然后开始遍历比较 1 若 下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间 取max( ed[i],tem_end ) 2 反之 这个

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +