問題
http://community.topcoder.com/stat?c=problem_statement&pm=12033&rd=15172
解き方
メモリも計算量も足りるので、正しく間違えないように実装すればよい。
コード
int p[1300][1300];
class RotatingBot {
public: int minArea(vector<int> moves) {
int n=moves.size();
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
memset(p,0,sizeof(p));
int minx=650,miny=650,maxx=650,maxy=650;
int x=650,y=650,d=0;
FORE(i,0,n){
FORE(j,0,moves[i]){
int nx=x+dx[d],ny=y+dy[d];
x=nx,y=ny;
minx=min(minx,x);
maxx=max(maxx,x);
miny=min(miny,y);
maxy=max(maxy,y);
}
d=(d+1)%4;
}
x=650,y=650,d=0;
p[x][y]=1;
FORE(i,0,n){
FORE(j,0,moves[i]){
int nx=x+dx[d],ny=y+dy[d];
if(p[nx][ny]==1)return -1;
x=nx,y=ny;
p[x][y]=1;
}
int xx=x+dx[d],yy=y+dy[d];
if(!(xx<minx || xx>maxx || yy<miny || yy>maxy || p[xx][yy]==1 || i==n-1)){
return -1;
}
d=(d+1)%4;
}
return (maxx-minx+1)*(maxy-miny+1);
}
};
class RotatingBot {
public: int minArea(vector<int> moves) {
int n=moves.size();
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
memset(p,0,sizeof(p));
int minx=650,miny=650,maxx=650,maxy=650;
int x=650,y=650,d=0;
FORE(i,0,n){
FORE(j,0,moves[i]){
int nx=x+dx[d],ny=y+dy[d];
x=nx,y=ny;
minx=min(minx,x);
maxx=max(maxx,x);
miny=min(miny,y);
maxy=max(maxy,y);
}
d=(d+1)%4;
}
x=650,y=650,d=0;
p[x][y]=1;
FORE(i,0,n){
FORE(j,0,moves[i]){
int nx=x+dx[d],ny=y+dy[d];
if(p[nx][ny]==1)return -1;
x=nx,y=ny;
p[x][y]=1;
}
int xx=x+dx[d],yy=y+dy[d];
if(!(xx<minx || xx>maxx || yy<miny || yy>maxy || p[xx][yy]==1 || i==n-1)){
return -1;
}
d=(d+1)%4;
}
return (maxx-minx+1)*(maxy-miny+1);
}
};