Problem
Tetris is a famous video game that almost everyone has played it. In this problem, you need to simulate a simplified version of it.
In our version, the game is played in a W by H field with gravity. At the beginning, the field is empty. Then the tetrominos start to fall from above top of the field to bottom of the field, one by one. Each tetromino will stop as soon as it touches some other tetrominos or bottom of the field.
One interesting feature of the game is called "line clearing". A line will be cleared as soon as it is filled by tetrominos. More than one line may be cleared at a time. For example:
|..............| |..............| |..............|
|.............o| |..............| |..............|
|.............o| |..............| |..............|
|.............o| |..............| |..............|
|.............o| |..............| |..............|
|..xx..........| --> |..xx..........| --> |..............|
|xxxxxxxxxxxxx.| |xxxxxxxxxxxxxo| |..............|
|xxxxxxxxxxxxx.| |xxxxxxxxxxxxxo| |..xx..........|
|xx..xxxxxxxxx.| |xx..xxxxxxxxxo| |xx..xxxxxxxxxo|
|xxxxxxxxxxx...| |xxxxxxxxxxx..o| |xxxxxxxxxxx..o|
---------------- ---------------- ----------------
Falling Stopped Cleared 2 lines
Note that in this simplified version, the "floating" tetromino blocks won't continue to fall after lines are cleared. This is why the top-most two squares will keep in such position. Consequently, cascade clearing won't happen, even though it would happen in the original version of Tetris.
The game ends when all the given tetrominos are placed, or the current tetromino cannot be placed due to the height limit of the field is reached.
In this problem, each tetromino will has its type, rotation and falling position told by the input. They will start to fall from the above of the field. Your goal is to simulate and get the final result of each play.
Input
We have 7 types of tetromino:
1 2 3 4 5 6 7
x x x x xx x x
xx xx x x xx x xxx
x x xx xx x
x
Rotation of a tetromino is represented by a number r. r can be 0, 1, 2 or 3. Rotation is counterclockwise. For example:
r=0 r=1 r=2 r=3
x x xxx x
xxx xx x xx
x x
x xx x xx
xx xx xx xx
x x
The horizontal falling position is represented by a number x. It is the coordinate of the lower left square of a tetromino's bounding box. Here x starts from 0.
The first line of the input gives the number of test cases, T. For each test case, the first line of input has 3 integers, W, H, N. W is the width, H is the height and N is the number of blocks that are going to fall.
Then N lines below, each line has 3 integers, ti, ri, xi. ti tells the tetromino type. ri is the rotation of this tetromino. xi is the horizontal falling position of this tetromino. It is guaranteed that xi will make the tetromino inside the field, horizontally.
Output
For each test case, first output one line containing "Case #i:", where i is the test case number (starting from 1). And then, if the game ends before the N blocks, output "Game Over!"(without quotes). Otherwise, output the game field's final state, which should have Hlines, each has W characters. Each character can be '.' or 'x'.
Limits
1 <= T <= 100
1 <= ti <= 7
0 <= ri < 4
Small dataset
4 <= W <= 20
1 <= H <= 20
0 <= N <= 100
Large dataset
4 <= W <= 100
1 <= H <= 100
0 <= N <= 5000
Sample
解法：本题是关于俄罗斯方块的，说些题外话，个人感觉Google出题还是非常有意思的，会结合很多很有趣的事情，不像Microsoft，笔试题看上去略显死板，一看就是笔试题，偶尔就算结合一些小事情，也结合的那么生硬，没有Google融合的这么完美，而且不喜欢Microsoft的一点是，笔试结束后没有办法练习了，不像Google笔试结束后还继续开放。
啰嗦多了，说正题了，这道题不是很难，但是很麻烦，做这道题的时候千万不要尝试真的让每个方块都一格一格下落，这是最蠢的办法，就算真的做出来了，效率也会非常低。
1. 放置。这道题可以记录每列的当前高度，这样当方块在本列下落的时候，直接尝试把方块放在这个高度，如果不行再往上查询，找一个可以放的高度，但是需要注意，如果方块是3*2的时候，需要在这个方块占据的3列均进行查询，找一个可以放置最低高度，而且找到的这个高度必须小于这3列原先的高端(你问为什么？因为题目没有告诉我们方块可以有可以穿墙的超能力啊)。
2. 更新列高度。放置好了之后要对方块覆盖的这几列的高度进行更新。
(此处要记得检查游戏是否已经结束，就是是否有元素超出了高度，但是个人认为这个应该在消去之后检测，依稀记得俄罗斯方块是消去之后再检测到超出高度之后才算Game Over的，但是google这题的要求是放下方块之后只要检测到超出了高度就算Game Over)。
3. 尝试消去。然后要尝试进行消去。
3.1 下落。消去之后的下落是个问题，我这边是记录了当前这行消去之后应该落在哪一行(此处一定要注意，消去的那行一定要清掉，因为消去的很有可能是最上面的一行，如果不清数据，数据直接就乱掉了。)。
3.2 重新计算高度。此处需要重新计算高度，为什么？因为消去了几行，那直接删掉消去的行数不就行了么？但是有可能消去那行下面都是空的呢？所以需要针对那些下面是空行的重新计算其有效高度。(当然，你也可以把第2步省略掉，这里抛弃全部的高度数据，直接全部从最开始重新计算，也是可行，但是个人总感觉效率偏低，因为下面空着的概率毕竟不是特别大，不可能每列都空着，除非非常*的堆出了类似于
＃＃＃＃＃＃＃＃＃＃＃＃
＃ ＃ ＃
＃ ＃ ＃
＃ ＃ ＃
...........................................
＃ ＃ ＃
＃ ＃ ＃
＃ ＃ ＃
这样的形状，对于这样的玩家，我只想说，你是处女座的吧。。玩个俄罗斯方块也是够拼的。)
4. 检测游戏是否已经结束。其实就是检测是否超出了游戏区域的高度。
然后循环做这4步。
具体代码如下，大小集合通用：
#include <iostream>
#include <fstream>
using namespace std;
#define POOLSIZE 110
int pool[POOLSIZE][POOLSIZE];
int volume[POOLSIZE];
int newRows[POOLSIZE];
class Tetro
{
public:
int row, col;
int data[4][4];
int rowRota, colRota;
int rotatedData[4][4];
Tetro()
{
row = 0; col = 0;
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
data[i][j] = 0;
}
void SetType(int type)
{
switch(type)
{
case 1:
{
// *
// **
// *
row = 3; col = 2;
data[0][0] = 1;
data[1][0] = 1; data[1][1] = 1;
data[2][1] = 1;
}
break;
case 2:
{
// *
// **
// *
row = 3; col = 2;
data[0][1] = 1;
data[1][0] = 1; data[1][1] = 1;
data[2][0] = 1;
}
break;
case 3:
{
// *
// *
// **
row = 3; col = 2;
data[0][0] = 1;
data[1][0] = 1;
data[2][0] = 1; data[2][1] = 1;
}
break;
case 4:
{
// *
// *
// **
row = 3; col = 2;
data[0][1] = 1;
data[1][1] = 1;
data[2][0] = 1; data[2][1] = 1;
}
break;
case 5:
{
// **
// **
row = 2; col = 2;
data[0][0] = 1; data[0][1] = 1;
data[1][0] = 1; data[1][1] = 1;
}
break;
case 6:
{
// *
// *
// *
// *
row = 4; col = 1;
data[0][0] = 1;
data[1][0] = 1;
data[2][0] = 1;
data[3][0] = 1;
}
break;
case 7:
{
// *
// ***
row = 2; col = 3;
data[0][1] = 1;
data[1][0] = 1; data[1][1] = 1; data[1][2] = 1;
}
break;
}
}
void setRotation(int rotation)
{
if (rotation == 0)
{
rowRota = row; colRota = col;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
rotatedData[i][j] = data[i][j];
}
}
}else if (rotation == 1)
{
// 第一列变为最后一行，最后一列转换为第一行
rowRota = col; colRota = row;
for (int j = 0; j < col; j++)
{
int rowtmp = col - j - 1;
for (int i = 0; i < row; i++)
{
rotatedData[rowtmp][i] = data[i][j];
}
}
}else if (rotation == 2)
{
// 对角交换
rowRota = row; colRota = col;
for (int i = 0; i < row; i++)
{
int rowtmp = row - i - 1;
for (int j = 0; j < col; j++)
{
int coltmp = col - j - 1;
rotatedData[rowtmp][coltmp] = data[i][j];
}
}
}else if (rotation == 3)
{
// 第一列变为第一行，并进行翻转，最后一列变为最后一行，并进行翻转
rowRota = col; colRota = row;
for (int j = 0; j < col; j++)
{
for (int i = 0; i < row; i++)
{
int coltmp = row - i - 1;
rotatedData[j][coltmp] = data[i][j];
}
}
}
}
};
class Tetromino
{
public:
Tetro tetroData[4];
Tetromino(){};
void setTetrominoType(int type)
{
for (int i = 0; i < 4; i++)
{
tetroData[i].SetType(type);
tetroData[i].setRotation(i);
}
}
};
Tetromino data[7];
int W, H;
int printState = 0;
void init()
{
for (int i = 0; i < 7; i++)
{
data[i].setTetrominoType(i+1);
}
}
void reset()
{
for (int i = 0; i < POOLSIZE; i++)
{
for (int j = 0; j < POOLSIZE; j++)
{
pool[i][j] = 0;
}
}
for (int i = 0; i < POOLSIZE; i++)
{
volume[i] = 0;
}
}
void output()
{
int startrow = POOLSIZE;
for (int i = H; i > 0; i--)
{
int row = startrow - i;
for (int j = 0; j < W; j++)
{
if (pool[row][j])
{
cout << 'x';
}else
{
cout << '.';
}
}
cout << endl;
}
}
int canPut(Tetro &te, int fallingpos, int height)
{
// 此处判断要注意
// **
// *
// *
// 下落的时候的判断
// ****
// ***
// ****
// ****
// *****
// 落到这种地方的时候一定要注意，要防止穿过
int newTop = height + te.rowRota;
for (int i = 0; i < te.colRota; i++)
{
if (volume[fallingpos + i] >= newTop)
{
return 0;
}
}
int poolStartRow = POOLSIZE - height - te.rowRota;
for (int i = 0; i < te.rowRota; i++)
{
int poolRow = poolStartRow + i;
for (int j = 0; j < te.colRota; j++)
{
if (pool[poolRow][fallingpos + j] && te.rotatedData[i][j])
{
return 0;
}
}
}
return 1;
}
void clearTetro()
{
int poolStartRow = POOLSIZE - 1;
int elimatenum = 0;
for (int i = 0; i < H; i++)
{
int row = poolStartRow - i;
int elimate = 1;
for (int j = 0; j < W; j++)
{
if (pool[row][j] == 0)
{
elimate = 0;
break;
}
}
if (elimate)
{
elimatenum++;
// must set this line to POOLSIZE, then this line will set to be 0.
// or this line will overwrite other line.
newRows[row] = POOLSIZE;
}else
{
newRows[row] = row + elimatenum;
}
}
for (int i = 0; i < H; i++)
{
int row = poolStartRow - i;
int newrow = newRows[row];
if(row != newrow)
{
if(newrow < POOLSIZE)
{
for(int j = 0; j < W; j++)
{
pool[newrow][j] = pool[row][j];
// 移动完了之后，这里需要把原始的清掉
pool[row][j] = 0;
}
}else
{
// 这里并没有办法把所有该清掉的元素给清掉，因为有些需要清掉的是已经移下去的，而不是被消除的那些行
// 所以需要在上面的分支把原始的数据清掉
for(int j = 0; j < W; j++)
{
pool[row][j] = 0;
}
}
}
}
for(int i = 0; i < W; i++)
{
volume[i] -= elimatenum;
volume[i] = volume[i] < 0 ? 0 : volume[i];
// 消去的时候可能会造成此高度的改变，比如说消去行下面是空的，那么其可放置高度就会改变，此时需要重新计算
if (volume[i] > 0)
{
// here it should be plus 1, not minus 1, so (POOLSIZE - 1) - volume[i] + 1,
// because it should be the next row, and the next row is the +1 row.
for (int j = POOLSIZE - volume[i]; j < POOLSIZE; j++)
{
if (pool[j][i] == 0 && volume[i] != 0)
{
volume[i]--;
}else
break;
}
}
}
}
int isGameOver()
{
for (int i = 0; i < W; i++)
{
if (volume[i] > H)
{
return 1;
}
}
return 0;
}
int putTetro(int type, int rotation, int fallingpos)
{
Tetro &te = data[type - 1].tetroData[rotation];
// find the put height.
int putHeight = POOLSIZE;
for (int i = 0; i < te.colRota; i++)
{
int curHeight = volume[fallingpos + i];
while (!canPut(te, fallingpos, curHeight))
{
curHeight++;
}
if (curHeight < putHeight)
{
putHeight = curHeight;
}
}
// put the tetro.
int poolStartRow = POOLSIZE - putHeight - te.rowRota;
for (int i = 0; i < te.rowRota; i++)
{
int poolRow = poolStartRow + i;
for (int j = 0; j < te.colRota; j++)
{
pool[poolRow][fallingpos + j] = pool[poolRow][fallingpos + j] || te.rotatedData[i][j];
}
}
for (int j = 0; j < te.colRota; j++)
{
for (int i = 0; i < te.rowRota; i++)
{
if (te.rotatedData[i][j])
{
// here the volume must be putHeight plus increased height,
// but not the origin volume plus the increased height.
volume[fallingpos + j] = putHeight + te.rowRota - i;
break;
}
}
}
// check game over
// 只要有方块放在了区域外，不管消去之后是不是可以不停留在方块外，此时都应该算作gameover
if (isGameOver())
{
return 1;
}
// clear tetro
clearTetro();
if (printState)
{
cout << "current state:" << endl;
output();
}
// check game over
return isGameOver();
}
// return true if game over.
int process()
{
int gameover = 0;
int tetroNum, type, rotation, fallingpos;
cin >> tetroNum;
for (int k = 0; k < tetroNum; k++)
{
cin >> type >> rotation >> fallingpos;
if(gameover)
continue;
if (putTetro(type, rotation, fallingpos))
{
gameover = 1;
}
}
return gameover;
}
int main()
{
//
int T, idx = 0;
cin >> T;
init();
while(idx < T)
{
idx++;
reset();
cout << "Case #" << idx << ":" << endl;
cin >> W >> H;
// if (idx == 75)
// {
// printState = 1;
// }else
// {
// printState = 0;
// }
if (process())
{
cout << "Game Over!" << endl;
}else
{
output();
}
}
return 0;
}