Analysis: Bovine Ballet by Fatih Gelgi
In this problem, a trivial solution is to keep the feet positions and apply instructions one by one. After each instruction, the corner coordinates of the rectangular stage are updated. Note that we cannot mark the feet position on a matrix since the matrix may be excessively large and doesn't fit in the memory (ex. an input that has 500 FRFs and FRP,RRP alternates 250 times).
at the beginning, we need to assign initial positions to the feet. Let's say:
y x
FL (0,0)
FR (0,1)
RL (1,0)
RR (1,1)
Without rotation, moves are straightforward:
When we include rotation, the moves will change with respect to the current direction. We have 16 different cases in total -- 4 moves per direction. One idea is to write all cases one by one. However, we will work on a more elegant idea. Let's numerate the moves first - {0:forward, 1:right, 2:back, 3:left}. Notice that they in clockwise order. Let's numerate the directions again in clockwise order as the second step - {0:north, 1:east, 2:south, 3:west}. Now, consider the following instructions:
0) Initially: .. .. .. .. .. .. .. .. (facing north) .. .. FL FR .. .. RL RR 1) FRF: .. .. .. .. .. .. .. FR (facing north) .. .. FL .. .. .. RL RR 2) FRP: .. RL FL .. .. RR .. FR (facing east) .. .. .. .. .. .. .. .. 3) RRF: .. RL FL .. .. .. RR FR (facing east) .. .. .. .. .. .. .. .. 4) RLP: .. RL .. .. RR FL .. .. (facing south) FR .. .. .. .. .. .. .. 5) FRF: .. RL .. .. RR FL .. .. (facing south) .. .. .. .. FR .. .. ..
You can observe that the moves shift by rotations. In other words, forward becomes right, right becomes back, back becomes left, left becomes forward in one rotation. For instance, Bessie moves forward (MOVE=0) in steps 1,3 and 5. In the first one, the direction is north (DIR=0). In steps 3 and 5, the directions are east (DIR=1) and south (DIR=2). Forward move (MOVE=0) means to move right (MOVE=1) and back (MOVE=2) when facing east (DIR=1) and south (DIR=2) respectively. As a summary, we can calculate the absolute direction of the current move by MOVE = (MOVE + DIR) % 4.
Now, the issue is to do the rotation. We need to calculate the new positions for the feet. Consider the following rotation:
1) FRF: -2 -1 0 1 -2 .. .. .. .. -1 .. .. .. FR 0 .. .. FL .. 1 .. .. RL RR 2) FRP: -2 -1 0 1 -2 .. RL FL .. -1 .. RR .. FR (facing east) 0 .. .. .. .. 1 .. .. .. ..
New coordinate of a foot (y1,x1) is (y0+x1-x0,x0+y0-y1) where (y0,x0) is the position of the pivot foot. In the example above, the rotation is as follows:
initial position after rotation ------------ ------------ FL (0,0) (-1+0-1,1-1-0)=(-2,0) FR (-1,1) (-1,1) RL (1,0) (-1+0-1,1-1-1)=(-2,-1) RR (1,1) (-1+1-1,1-1-1)=(-1,-1)
The solution requires O(N) time. The sample code is provided below:
#include <fstream>
#include <algorithm>
using namespace std;
const int d[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; // (dy,dx)
{0:forward,1:right,2:back,3:left}
struct Point { int y,x; }
foot[4]={{0,0},{0,1},{1,0},{1,1}}; // initial feet positions
int dir; // {0:north,1:west,2:south,3:east}
int miny,minx,maxy,maxx; // min - max coordinates of the area
int move(string s)
{
// determine the foot
int f=0;
if (s[0]=='F' && s[1]=='R') f=1;
else if (s[0]=='R')
if (s[1]=='L') f=2;
else f=3;
// clockwise rotation
if (s[2]=='P')
{
for (int i=0; i<4; i++)
{
int ny=foot[f].y+foot[i].x-foot[f].x;
int nx=foot[f].x+foot[f].y-foot[i].y;
foot[i].y=ny,foot[i].x=nx;
}
dir=(dir+1)%4; // rotate direction clockwise
}
// move
else
{
// get the relative direction
int m=0;
if (s[2]=='R') m=1;
if (s[2]=='B') m=2;
if (s[2]=='L') m=3;
m=(m+dir)%4; // calculate the absolute direction
foot[f].y+=d[m][0];
foot[f].x+=d[m][1];
// check if Bessie trips
for (int i=0; i<4; i++)
if (f!=i && foot[f].y==foot[i].y && foot[f].x==foot[i].x)
return 0;
}
// update minimum size rectangle
for (int i=0; i<4; i++)
{
if (miny>foot[i].y) miny=foot[i].y;
if (maxy<foot[i].y) maxy=foot[i].y;
if (minx>foot[i].x) minx=foot[i].x;
if (maxx<foot[i].x) maxx=foot[i].x;
}
return 1;
}
int main()
{
ifstream fin("ballet.in");
ofstream fout("ballet.out");
int n,valid=1;
fin >> n;
string inst;
for (int i=0; i<n; i++)
{
fin >> inst;
if (!(valid=move(inst))) break;
}
if (valid)
fout << (maxy-miny+1)*(maxx-minx+1) << endl;
else
fout << -1 << endl;
fin.close();
fout.close();
}