2014
03-13

# Automatic Tetris Player

A random sequence of tetrominoes (sometimes called "tetrads" in older versions)-shapes composed of four square blocks each-fall down the playing field (a rectangular vertical shaft, called the "well" or "matrix"). The object of the game is to manipulate these tetrominoes, by moving each one sideways and rotating it by 90 degree units, with the aim of creating a horizontal line of blocks without gaps. When such a line is created, it disappears, and any block above the deleted line will fall. As the game progresses, the tetrominoes fall faster, and the game ends when the stack of tetrominoes reaches the top of the playing field and no new tetrominoes are able to enter.

– Wikipedia (http://en.wikipedia.org/wiki/Tetris)

The seven one-sided tetrominoes below are represented by I, J, L, O, S, T, Z from first row to the second, left to right. Look at their shapes, then you’ll realize why they’re called this way.

Your task is to implement an automatic tetris player. You’ll be given a sequence of blocks, and your objective is to minimize the sum of squares of column heights. By "height", we mean the row number of the topmost non-empty unit block of that column. Rows are numbered 1, 2, 3, …, in a bottom-up order. Technically, if we denote the height of column i by hi, you should minimize sum{(hi)2}.

For simplicity, assume each block is falling from high enough, and you cannot control the block anymore, once you decide its rotating and horizontal position. Note that you cannot mirror the blocks, only horizontal moving and rotating is permitted.

The field is always 5 columns wide. When a line of unit blocks are eliminated, the vertical position of everything above the line is decreased by 1. This is the most widely used algorithm. But the resulting board may looks strange, since things can "float up in the sky", see below.

The first line contains a single integer T (T <= 20), the number of test cases. Each case contains a single line of a string, representing the block sequence. There will be no more than 5 blocks, each of them will be one of I, J, L, O, S, T and Z.

The first line contains a single integer T (T <= 20), the number of test cases. Each case contains a single line of a string, representing the block sequence. There will be no more than 5 blocks, each of them will be one of I, J, L, O, S, T and Z.

3
LLLLO
IJ
STZ

Case 1: 0
Case 2: 3
Case 3: 15

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int MAXN=10;
int hei[10];
int mp[300];
int a[30][5];
int p[100][30];
char s[100];
int first,anss;
int Cnt[10]={2,4,4,1,2,4,2};
int Dx[7][4]=
{
0,0,0,0,
0,-1,-1,-1,
0,-1,-1,-1,
0,0,-1,-1,
0,0,-1,-1,
0,-1,-1,-1,
0,0,-1,-1
};
int Dy[7][4]=
{
0,1,2,3,
0,0,1,2,
0,-2,-1,0,
0,1,0,1,
0,1,-1,0,
0,-1,0,1,
0,1,1,2
};
int rotx(int x,int y,int rot)
{
if (rot==0) return x;
if (rot==1) return y;
if (rot==2) return -x;
if (rot==3) return -y;
}
int roty(int x,int y,int rot)
{
if (rot==0) return y;
if (rot==1) return -x;
if (rot==2) return -y;
if (rot==3) return x;
}
bool set(int now,int id,int pos,int rot)
{
for (int i=0; i<4; i++)
{
int dx1=Dx[id][i];
int dy1=Dy[id][i];
int dx=rotx(dx1,dy1,rot);
int dy=roty(dx1,dy1,rot);
if (pos+dy<0||pos+dy>=5) return false;
}
int target=0;
for (int ii=MAXN; ii>=0; ii--)
{
for (int i=0; i<4; i++)
{
int dx1=Dx[id][i];
int dy1=Dy[id][i];
int dx=rotx(dx1,dy1,rot);
int dy=roty(dx1,dy1,rot);
if (ii+dx<0)
{
target=ii+1;
break;
}
if (a[ii+dx][pos+dy]==1)
{
target=ii+1;
break;
}
}
if (target!=0) break;
}
//printf("%d %d\n",pos,target);
for (int i=0; i<4; i++)
{
int dx1=Dx[id][i];
int dy1=Dy[id][i];
int dx=rotx(dx1,dy1,rot);
int dy=roty(dx1,dy1,rot);
//printf("%d %d\n",pos+dx,target+dy);
a[target+dx][pos+dy]=1;
}
p[now][0]=target;
p[now][1]=0;
for (int i=MAXN; i>=0; i--)
{
bool find=true;
for (int j=0; j<5; j++)
if (a[i][j]!=1) find=false;
if (find)
{
p[now][p[now][1]+2]=i;
for (int j=i; j<MAXN; j++)
for (int k=0; k<5; k++)
a[j][k]=a[j+1][k];
for (int k=0; k<5; k++)
a[MAXN][k]=0;
p[now][1]++;
}
}
return true;
}
void remove(int now,int id,int pos,int rot)
{
for (int ii=p[now][1]-1; ii>=0; ii--)
{
int line=p[now][ii+2];
for (int i=MAXN; i>line; i--)
for (int j=0; j<5; j++)
a[i][j]=a[i-1][j];
for (int j=0; j<5; j++)
a[line][j]=1;
}
int target=p[now][0];
for (int i=0; i<4; i++)
{
int dx1=Dx[id][i];
int dy1=Dy[id][i];
int dx=rotx(dx1,dy1,rot);
int dy=roty(dx1,dy1,rot);
a[target+dx][pos+dy]=0;
}
}
void dfs(int now,int end)
{
if (now==end)
{
int ans=0;
for (int i=0; i<5; i++)
{
int max=0;
for (int j=MAXN; j>=0; j--)
if (a[j][i]==1)
{
max=(j+1);
break;
}
ans+=max*max;
}
if (first||ans<anss)
anss=ans;
first=0;
return;
}
for (int i=0; i<5*Cnt[mp[s[now]]]; i++)
{
int x=i/Cnt[mp[s[now]]];
int rot=i%Cnt[mp[s[now]]];
if (set(now,mp[s[now]],x,rot))
{
dfs(now+1,end);
remove(now,mp[s[now]],x,rot);
}
}
}

int main()
{
mp['I']=0;
mp['J']=1;
mp['L']=2;
mp['O']=3;
mp['S']=4;
mp['T']=5;
mp['Z']=6;
int t;
scanf("%d",&t);
for (int ii=1; ii<=t; ii++)
{
scanf("%s",s);
memset(a,0,sizeof(a));
first=1;
int len=strlen(s);
dfs(0,len);
printf("Case %d: %d\n",ii,anss);
}
return 0;
}