1026 . Exciting Time
Description
It’s exciting time! Now let’s consider the most famous video game in the world:
Tetris.
Tetris is a puzzle video game originally designed and programmed by Alexey
Pajitnov. It was created on June 6, 1984. The game is available for nearly every
video game console and computer operating system, as well as devices such as
graphing calculators, mobile phones, portable media players, PDAs and even as
an Easter egg on non-media products like oscilloscopes.
Some random tetrominoes (shapes each composed of four square blocks) will fall
down sequentially into the playing field. The objective of the game is to manipulate
those tetrominoes, by moving each one sideways and/or rotating it, with the aim
of creating a horizontal line of blocks without gaps. When such a line is created,
it disappears, and any block above that line will fall down respectively. See
the sample test case for further details.
Tetris game manuals refer to the seven one-side tetrominoes in Tetris as I,
J, L, O, S, T and Z (due to their resembling letters of the alphabet). All are
capable of single and double clears. I, J and L are able to clear triples. Only
the I tetromino has the capacity to clear four lines simultaneously, and this
is referred to as a “tetris”.
Wikipedia (http://en.wikipedia.org/wiki/Tetris)
The scoring formula for the majority of Tetris products is based on the idea
that more difficult line clears should be awarded more points. Specifically, a
single clear will be awarded 100 points, 250 points for a double clear, 400 points
for a triple clear, and 1000 points for a “tetris”.
Now you are given the width of the playing field and a sequence
of tetrominoes with the position and degrees it rotated. The task is to calculate
how many points will be awarded.
You can assume the playing field is high enough, so that tetrominoes will not
overlap each other even when a tetromino is created at the top of the playing
field.
Input Format
There are multiple test cases.
The first line of the input contains an integer T, meaning the number of the
test cases.
The first line of each case contains two integers W and N (1≤W≤30000, 0≤N≤30000), where W is the width of the playing field and N is the number
of tetrominoes.
Then N lines follow. Each line contains the description of a single tetromino.
The type of the tetromino (I, J, L, O, S, T or Z) comes first, followed by an
integer ID, meaning the id of the column of the leftmost square block in the
tetromino. The columns are numbered in increasing order from left to right,
beginning with zero. The last number shows the degree the tetromino should be
rotated; it can only be 0, 90, 180 or 270. The one with 0-degree rotation is shown
in the above picture.
Note that the rotate operations are in clockwise. And the order
of tetrominoes is the same as the input sequence.
See the sample input for further details.
Output Format
For each test case you should output three lines.
The first line contains the case number.
The second line contains a single integer which is the points awarded in total.
The third line contains W integers, the i-th number is the height of the highest
square block in the i-th column, separated by a single whitespace.
Sample Input 1
2 6 9 I 0 0 S 3 90 T 4 270 J 0 0 J 2 90 S 0 0 Z 3 0 O 0 0 L 4 270 1 1 I 0 90
Sample Output 1
Case #1: 200 6 6 4 4 6 6 Case #2: 1000 0
Hints
The final state of the game field is shown below.
Problem Source
Migrated from old NTUJ.
2009Shanghai
Subtasks
| No. | Testdata Range | Score |
|---|