Wow! Such Tetris!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
Tetris is a puzzle video game released in 1984. It¡¯s so popular that it¡¯s available on nearly every electronic device that has a screen.
In this game, the playfield is a bucket (or say ¡°matrix¡±) formed by small squares (blocks) of equal size. A sequence of ¡°Tetrominoes¡± (geometric shapes composed of four small squares each) spawn one by one on the top of the matrix. The player can manipulate the active Tetromino by moving it left, right or down, and rotating it by 90 degrees clockwise or counter- clockwise. When a Tetromino touches the bottom of the matrix or blocks places before (causing collision when falling one more square), if you let it fall down again, it locks on the position and is not operatable anymore. A new active Tetromino will appear on the top at this time.
As the game progresses, there will be more and more blocks stacked in the matrix. If any horizontal line of the matrix are completely filled by blocks when a Tetromino locks, these lines will disappear (called ¡°line clear¡±), and blocks above the deleted lines will fall down. When the stack of the blocks reached the top of the matrix which caused a new Tetromino entering collides with them, the game ends.
Isn¡¯t it fun?
In this problem, you are given a matrix with some blocks already there, and the next two Tetrominoes to enter the matrix in order. You are required to calculate how many lines at most can be cleared by placing them into the matrix. If no lines can be cleared no matter how you place them, output 0. If the you can¡¯t avoid getting ¡°gameover¡± no matter how you place them, output -1.
In this problem, the ¡°visible¡± size of the matrix is 10w ¡Á20h. The input data also describes all blocks in the visible area. The left bound, right bound and bottom bound are all solid. When any part of a Tetromino exceeds those bounds, it¡¯ll be considered colliding with the matrix. The upper-left and upper-right area are considered extension of the left and right bound, they are also solid. However, the area beyond the top of the matrix is considered empty, and blocks can be placed in the invisible area. They¡¯ll exist as is and fall down when there¡¯s line clear under them. They won¡¯t cause gameover until they collide with a new spawning Tetromino. When a new Tetromino spawns, it¡¯s always beyond the visible area. The detailed coordinates are specified below. After placing the 2 pieces, it¡¯s considered no more Tetromino is entering. Thus, only the second Tetromino may cause gameover. The only condition to cause gameover is a new spawning Tetromino colliding with blocks in the matrix on its initial position.
After line clears, there may be some single pieces of blocks floating in the air. A line clear will only remove the full lines, and the blocks above will fall down by exactly how many lines are cleared below. The floating pieces will not continue falling.
There are seven types of Tetromino in total, called I, O, T, S, Z, J, L correspondingly based on their shapes. An active Tetromino moves by single grids. If you want to move a Tetromino by several grids in one direction, it successes only when each step successes. The rotation of Tetrominoes successes when the shape after rotating, on its coordinates before rotating, doesn¡¯t cause collision. It doesn¡¯t require verification of physical continuous rotation. Thus, it allows some Tetrominoes to ¡°spin¡± into some slots which are unreachable by only shifting.
For instance:
...##..... ...##O.... ...##.....
####...### ####.OO### ####OOO###
#####.#### #####O#### #####O####
In the figure above, ¡°O¡± denotes the active Tetromino, ¡°#¡± denotes fixed blocks, ¡°.¡± denotes empty grids. You may let a right-facing T Tetromino fall down to the correct position, and perform a clockwise rotation, then 2 lines can be cleared.
If the Tetromino collides with something after moving or rotating, the operation is can- celled.
/* In modern versions of Tetris games, even when there¡¯s collision after rotation, if mov- ing around to avoid collision is possible, the rotation will still success, with the Tetromino automatically moved to a valid position. This move is called a ¡°wallkick¡±, which allows the Tetromino to twist into more tight spots. For simplicity, in this problem, wallkick is not considered, i.e. a rotation fails once it causes collision. */
The positions of a piece rotating at a fixed point is specified as following. You may copy those strings for implementation of rotations. The initial orientation of each new Tetromino is the leftmost one. And the shape of those rotated clockwise by 1,2,3 times follows. Performing clockwise rotation again after 3 rotations turns it back to the leftmost one. The same applies for counter-clockwise rotations.
In the figure below, ¡°o¡± denotes visible area of the matrix, ¡°*¡± denotes the the initial position of new Tetrominoes, ¡°.¡± denotes invisible area.
"...****..."
"...****..."
"ooo****ooo"
"ooo****ooo"
"oooooooooo"
"oooooooooo"
(16 lines omitted)
In this game, the playfield is a bucket (or say ¡°matrix¡±) formed by small squares (blocks) of equal size. A sequence of ¡°Tetrominoes¡± (geometric shapes composed of four small squares each) spawn one by one on the top of the matrix. The player can manipulate the active Tetromino by moving it left, right or down, and rotating it by 90 degrees clockwise or counter- clockwise. When a Tetromino touches the bottom of the matrix or blocks places before (causing collision when falling one more square), if you let it fall down again, it locks on the position and is not operatable anymore. A new active Tetromino will appear on the top at this time.
As the game progresses, there will be more and more blocks stacked in the matrix. If any horizontal line of the matrix are completely filled by blocks when a Tetromino locks, these lines will disappear (called ¡°line clear¡±), and blocks above the deleted lines will fall down. When the stack of the blocks reached the top of the matrix which caused a new Tetromino entering collides with them, the game ends.
Isn¡¯t it fun?
In this problem, you are given a matrix with some blocks already there, and the next two Tetrominoes to enter the matrix in order. You are required to calculate how many lines at most can be cleared by placing them into the matrix. If no lines can be cleared no matter how you place them, output 0. If the you can¡¯t avoid getting ¡°gameover¡± no matter how you place them, output -1.
In this problem, the ¡°visible¡± size of the matrix is 10w ¡Á20h. The input data also describes all blocks in the visible area. The left bound, right bound and bottom bound are all solid. When any part of a Tetromino exceeds those bounds, it¡¯ll be considered colliding with the matrix. The upper-left and upper-right area are considered extension of the left and right bound, they are also solid. However, the area beyond the top of the matrix is considered empty, and blocks can be placed in the invisible area. They¡¯ll exist as is and fall down when there¡¯s line clear under them. They won¡¯t cause gameover until they collide with a new spawning Tetromino. When a new Tetromino spawns, it¡¯s always beyond the visible area. The detailed coordinates are specified below. After placing the 2 pieces, it¡¯s considered no more Tetromino is entering. Thus, only the second Tetromino may cause gameover. The only condition to cause gameover is a new spawning Tetromino colliding with blocks in the matrix on its initial position.
After line clears, there may be some single pieces of blocks floating in the air. A line clear will only remove the full lines, and the blocks above will fall down by exactly how many lines are cleared below. The floating pieces will not continue falling.
There are seven types of Tetromino in total, called I, O, T, S, Z, J, L correspondingly based on their shapes. An active Tetromino moves by single grids. If you want to move a Tetromino by several grids in one direction, it successes only when each step successes. The rotation of Tetrominoes successes when the shape after rotating, on its coordinates before rotating, doesn¡¯t cause collision. It doesn¡¯t require verification of physical continuous rotation. Thus, it allows some Tetrominoes to ¡°spin¡± into some slots which are unreachable by only shifting.
For instance:
...##..... ...##O.... ...##.....
####...### ####.OO### ####OOO###
#####.#### #####O#### #####O####
In the figure above, ¡°O¡± denotes the active Tetromino, ¡°#¡± denotes fixed blocks, ¡°.¡± denotes empty grids. You may let a right-facing T Tetromino fall down to the correct position, and perform a clockwise rotation, then 2 lines can be cleared.
If the Tetromino collides with something after moving or rotating, the operation is can- celled.
/* In modern versions of Tetris games, even when there¡¯s collision after rotation, if mov- ing around to avoid collision is possible, the rotation will still success, with the Tetromino automatically moved to a valid position. This move is called a ¡°wallkick¡±, which allows the Tetromino to twist into more tight spots. For simplicity, in this problem, wallkick is not considered, i.e. a rotation fails once it causes collision. */
The positions of a piece rotating at a fixed point is specified as following. You may copy those strings for implementation of rotations. The initial orientation of each new Tetromino is the leftmost one. And the shape of those rotated clockwise by 1,2,3 times follows. Performing clockwise rotation again after 3 rotations turns it back to the leftmost one. The same applies for counter-clockwise rotations.
In the figure below, ¡°o¡± denotes visible area of the matrix, ¡°*¡± denotes the the initial position of new Tetrominoes, ¡°.¡± denotes invisible area.
"...****..."
"...****..."
"ooo****ooo"
"ooo****ooo"
"oooooooooo"
"oooooooooo"
(16 lines omitted)
Input
There are multiple test cases. Please process till EOF.
20 lines of strings of 10 chars each follows, representing the blocks those are already in the visible area of the matrix. The invisible area is considered empty. The char on the Y-th (downward from the top) line and the X-th (rightward from the left) column indicates the corresponding grid in the visible area. ¡°.¡± denotes an empty grid, ¡°#¡± denotes a block. no other chars will present. A string of 2 chars follows, representing the Tetrominoes to spawn in order. Either of them is one of I, O, T, S, Z, J, L, no other chars will present.
The next test case follows.
The input is guaranteed valid and there will be no filled line on initial.
20 lines of strings of 10 chars each follows, representing the blocks those are already in the visible area of the matrix. The invisible area is considered empty. The char on the Y-th (downward from the top) line and the X-th (rightward from the left) column indicates the corresponding grid in the visible area. ¡°.¡± denotes an empty grid, ¡°#¡± denotes a block. no other chars will present. A string of 2 chars follows, representing the Tetrominoes to spawn in order. Either of them is one of I, O, T, S, Z, J, L, no other chars will present.
The next test case follows.
The input is guaranteed valid and there will be no filled line on initial.
Output
Output one line for each test case, containing the maximum number of lines can be cleared in corresponding test case.
Sample Input
.......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ########.. #######... ########.. #########. TI .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... #########. ###.#####. ###.#####. #########. ###.###### ###.###### II
Sample Output
4 6