题目描述
[奶牛芭蕾]
https://www.acwing.com/problem/content/1961/
关键在于进行旋转操作和根据朝向调整移动方向
样例
输入
3
FRF
FRP
RLB
输出
16
重点1
旋转坐标公式, 点(x,y)
绕(x0,y0)
顺时针旋转$90°$,可以使用如下公式
x' = (y-y0)+x0
y' = -(x-x0)+y0
点(x',y')
即为旋转后新的点坐标
推导:
先考虑简单情况,即绕原点(0,0)
旋转
则(x,y)->(y,-x)
,自行画图可以得到
如果绕任意一点(x0,y0)
旋转,可以看成先将原点坐标平移到(0,0)
再将进行旋转操作
重点2
朝北,朝东,朝南,朝西分别用0,1,2,3
表示,则横、纵坐标x,y
的平移情况为,
注:-x
表示x--, y
不变,x
表示x++, y
不变。-y, y
同理
0 1 2 3
F y x -y -x
L -x y x -y
B -y -x y x
R x -y -x y
四方向偏移量int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
对应的为-x y x -y
对应L
,也就是说,只要操作为L
向左,无论朝向如何,
都可以直接套用四方向偏移量对坐标进行操作, 比如
FRL
表示前右脚向左,当dir = 0
即奶牛朝向北时,dx[dir] = -1, dy[dir] = 0
即前右脚x-1, y
不变,据此更新坐标即可
算法1
(暴力枚举) $O(n)$
直接读入操作进行模拟即可
时间复杂度
C++ 代码
#include <iostream>
#include <unordered_map>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n;
unordered_map<string,PII> feet;//存储4只脚的坐标
int minx,miny,maxx,maxy;//存储边界
void update(){//更新最大值和最小值
for(auto [k,v]: feet){
minx = min(minx, v.x);
miny = min(miny, v.y);
maxx = max(maxx, v.x);
maxy = max(maxy, v.y);
}
}
void rotate(string tmp, int& dir){//旋转操作,根据题意,旋转不会绊倒
int x0 = feet[tmp].x, y0 = feet[tmp].y;
for(auto& [k,v]: feet){
if(k==tmp) continue;
int x = v.x;
int y = v.y;
v.x = (y-y0)+x0;
v.y = -(x-x0)+y0;
}
update();//更新边界
dir = (dir+1)%4;
}
bool move(string tmp, char op, int dir){
PII t = feet[tmp];//无论朝向如何,移动的脚是不会变的
/*以下内容需要画图理解*/
int offset;
if(op=='L') offset = 4;
else if(op=='B') offset = 3;
else if(op=='R') offset = 2;
else offset = 1;
dir = (dir+offset)%4;//根据朝向调整移动的方向
int a = dx[dir], b = dy[dir];
t.x+=a,t.y+=b;
for(auto [k,v]: feet){
if(k==tmp) continue;
if(v.x==t.x&&v.y==t.y) return false;//判断绊倒的情况
}
feet[tmp] = t;//没有绊倒则更新牛脚的位置
update();//更新边界
return true;
}
int main()
{
//初始情况赋值
feet["FL"] = {0,1};
feet["FR"] = {1,1};
feet["RL"] = {0,0};
feet["RR"] = {1,0};
int dir = 0;
cin >> n;
for (int i = 0; i < n; i ++ ){
char a,b,op;
cin >> a >> b >> op;
string t = {a,b};
if(op=='P'){
rotate(t, dir);//旋转
}
else {
if(!move(t, op, dir)){//平移
cout<<-1;
return 0;
};
}
}
cout << (maxx-minx+1)*(maxy-miny+1);
return 0;
}