首页 > ACM题库 > HDU-杭电 > HDU 3250-Automatic Tetris Player[解题报告]HOJ
2014
03-13

HDU 3250-Automatic Tetris Player[解题报告]HOJ

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)

Task
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.

Selecting Frames

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.

Selecting Frames

输入:

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

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  3. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。