P2206

ran_qwq · 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;
}