自动搬运

查看原文

来自洛谷，原作者为

	ran_qwq debug 深入思考 只靠样例与自己！

搬运于2025-08-24 21:35:08，当前版本为作者最后更新于2022-11-05 14:54:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题做法显然，是模拟。

如果直接模拟的话代码会冗长，难以调试（这样的代码可以看下面的题解，下面会对这些题解进行一个对比）。

我们需要一些对长度的优化。

其实，四个蹄子的坐标并不需要用 $8$ 个变量，用一个数组记录当前位置，用 map 建立映射关系来查询。

我们在搜索时，会用数组记录四个方向。在这道题中，如果 Bessie 向北，她向前走是向北的；如果她向东，向前走就是向东，向右走就是向南。可以得出她实际上是向那走在模拟。

本题的难点在旋转上。估计不少人卡在了这里。

为了方便，我们假设支点坐标为 $(0,0)$，设要旋转的点坐标为 $(x,y)$。

根据小学课本可知，上图蓝线长度相等，等于 $x$；绿线长度相等，等于 $y$。则可看出，新点坐标为 $(y,-x)$。经举例得知此规律在任何情况都成立。

然后因为一开始设了支点坐标为 $(0,0)$，所以新点坐标应该加回支点坐标。

则代码写出来就很容易了。

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<map>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,dir,minx,maxx=1,miny,maxy=1,nx[4]={1,0,1,0},ny[4]={1,1,0,0};//这里设左后脚为原点
map<string,int> mp;
signed main()
{
	cin>>n;
	mp["FR"]=mp["F"]=0,mp["FL"]=mp["R"]=1,mp["RR"]=mp["B"]=2,mp["RL"]=mp["L"]=3;//用 map 建立映射关系
	for(int i=1;i<=n;i++)
	{
		string s,t;
		cin>>s,t=s[2],s.erase(2,1);//把字符串分离
		if(t!="P")//移动脚
			nx[mp[s]]+=dx[(mp[t]+dir)%4],ny[mp[s]]+=dy[(mp[t]+dir)%4];
		else
		{
			dir=(dir+1)%4;//方向改变
			int cx=nx[mp[s]],cy=ny[mp[s]];
			for(int i=0;i<4;i++)
			{
				int disx=nx[i]-cx,disy=ny[i]-cy;
				nx[i]=cx+disy,ny[i]=cy-disx;//新点坐标加回支点坐标
			}
		}
		for(int i=0;i<4;i++)
			minx=min(minx,nx[i]),maxx=max(maxx,nx[i]),miny=min(miny,ny[i]),maxy=max(maxy,ny[i]);//统计最小值
		for(int i=0;i<4;i++)//判断会不会绊倒
			for(int j=i+1;j<4;j++)
				if(nx[i]==nx[j]&&ny[i]==ny[j])
					cout<<-1,exit(0);
	}
	cout<<(maxx-minx+1)*(maxy-miny+1);
	return 0;
}