1443 . Jumbo Cubic Blokus
TopCoder
Description
Blokus is a board game about placing polyominoes (edge-connected squares) on a square board.
Now we consider its 3D version.
Initially, each player is given 11 pieces of polycubes as shown above.
These are the possible permutations of two to four unit cubes in 3D space.
Each player is associated with an unique color, and all the polycubes of a player are in that color.
The players take turns to put polycubes onto the board or on the top of other polycubes, one at a time.
The board is a shape on a X*Y square grids.
The polycubes can be rotated along any axes, but have to follow these rules when placing them:
- The edges of the polycubes must be parallel or vertical with respect to the axes of the board.
- The polycubes must be placed inside the shape totally.
That is, the projection of the polycubes on the board must lie completely inside the shape. - The first polycube of each player must touch at least one square of the board.
- The first polycube of all players (except the first one) must touch a polycube already on the board.
- After the first round, the polycubes that each player placed must touch one of the polycubes of the same color on the board.
- There should not be any empty space under the polycube that is going to be placed on the board.
Here "touch" means that two polycubes have a face in common.
As said, the players take turns to put polycubes.
The game starts with Player 1, then Player 2, ..., finally Player K, and then go back to Player 1 and so on.
If a player has already put all his polycubes onto the board, this player passes all the following turns.
If a player cannot legally place any of his polycubes, this player also passes all the following turns.
Otherwise, each player must put one polycube in each of his turn.
The game ends when no player can put more polycubes onto the board.
The score of a player is the number of square in his color when viewing the board from above
plus the number of his polycubes on the board.
Now, given a series of players' action, please calculate their scores after each action.
Also, please detect the illegal actions in the series.
The action includes a player ID, a description of a polycube, and a location on the board.
The illegal actions include the following:
- A player perform an action not in his turn, or in the turn that he should pass.
- A player put an polycube that he already put on the board.
- The polycube lies (partially or completely) outside the shape.
- Putting this polycube will make empty spaces under it.
The illegal actions should be detected and skipped.
They should not change any state of the game (the current player, the polycubes used, ... etc).
Input Format
The first line of the input contains a number T, indicating the number of test cases.
Two consecutive cases are separated by a blank line.
Each test case begins with four integers in a line, N, K, X, Y. N is the number of actions in the series.
Then board description follows.
The board description consists of X lines, each with Y characters.
The y-th character in the x-th line denotes whether the square (x,y) is in the shape ('.') or not ('#').
The following N lines describe the actions in time order.
Each line has three space-separated parts: a player ID, a polycube description, and a location.
The ID is an integer in [1,K].
The polycube description is in the form {x1y1z1,x2y2z2,...}, indicating the relative position (coordinate) of the unit cubes in this polycube.
The input guaratees that for each polycube description 0<= xi,yi,zi<=3 and min{xi}=min{yi}=min{zi}=0.
Finally the location is (x,y), which means the origin (0,0,0) in the polycube description should be mapped to (x,y,z*) on the board,
where z* is the minimum height that keep the polycube from coinciding with other polycubes. 0<= x<X, 0<= y<Y.
1<= N<= 600, 1<= K<= 50, 1<= X,Y<= 100.
Output Format
Please output one line for each action in each test case.
The line should contain "NO" if the action is illegal.
Otherwise the line should contain the score of each player separated by a whitespace, in increasing order of player ID.
Two consecutive test cases should be separated by a blank line.
Sample Input 1
2
15 2 4 5
.....
.....
.....
.....
1 {000,001,002,003} (1,2)
2 {011,010,001,000} (1,0)
1 {002,101,100,102} (1,1)
2 {000,010,020,011} (0,1)
1 {000,001,011,012} (0,1)
2 {000,100,101,010} (1,3)
1 {000,010,001,101} (1,3)
2 {000,100,101,110} (2,2)
1 {000,001,002,101} (2,2)
2 {111,011,001,000} (1,0)
1 {002,001,000} (0,3)
2 {001,002,010,011} (3,3)
1 {110,111,000,100} (2,0)
2 {002,100,101,102} (1,4)
1 {111,110,101,011} (2,3)
8 2 1 5
....#
2 {000,001} (0,1)
1 {000,010,020,011} (0,0)
2 {002,001,011,010} (0,2)
1 {000,001} (0,0)
2 {000,010,020} (0,0)
2 {001,010,011} (0,0)
1 {000,001,010,011} (0,1)
2 {001,011,020,021} (0,0)
Sample Output 1
2 0 2 3 5 2 5 6 8 4 8 8 12 5 12 9 15 7 13 10 15 9 15 11 19 11 18 14 NO NO 4 0 3 3 4 3 NO 2 6 NO 2 7
Hints
Figures of the board after each of the first 12 steps in the first test case.
The top-most corner is (0,0).
 |  |  |
 |  |  |
 |  |  |
 |  |  |
Problem Source
Migrated from old NTUJ.
Ferng
Subtasks
| No. | Testdata Range | Score |
|---|