Board Rotation
Time limit5sMemory limit512 MB
Rotate each board 90 degrees clockwise, let gravity settle the pieces, then report whether Red, Blue, both, or neither has K in a row.
- Level
Easy3 of 10
- Topics
- Simulation, Matrix, Brute force
- Solved
- No attempts yet
Problem
In the game of Join-K, players drop red and blue pieces into an N by N board. The board stands upright, so a dropped piece falls to the lowest empty cell of its column.
This position is legal.
.......
.......
.......
....R..
...RB..
..BRB..
.RBBR..
This position is not legal.
.......
.......
.......
.......
..BR...
...R...
.RBBR..
A '.' is an empty cell, an 'R' is a red piece, and a 'B' is a blue piece. The second board is illegal because the blue piece in the third column stayed above an empty cell instead of falling into it.
A player wins when K pieces of that player's colour stand in a row horizontally, vertically, or along either diagonal. For K equal to 4 the four orientations look like this.
R RRRR R... ...R
R .R.. ..R.
R ..R. .R..
R ...R R...
On the legal board above both players have two pieces in a row, and neither has three.
You are playing a game of Join-K and you have a plan. While your opponent looks away you rotate the whole board 90 degrees clockwise. Gravity then pulls every piece down in the new orientation.
Start:
.......
.......
.......
...R...
...RB..
..BRB..
.RBBR..
After the clockwise rotation:
.......
R......
BB.....
BRRR...
RBB....
.......
.......
After gravity:
.......
.......
.......
R......
BB.....
BRR....
RBBR...
You have time for one rotation before your opponent notices. Given a starting board, report which player or players have K pieces in a row once the rotation and gravity are finished.
Rules:
- You can rotate the board only once.
- Gravity acts only after the rotation is complete.
- Winners are checked only after gravity has finished.
Input
The first line holds the number of test cases T. Each test case begins with a line holding N and K. The next N lines hold exactly N characters each and give the starting board in the format used above.
Every starting board is a legal position that can occur in a game of Join-K. In particular, neither player already has K pieces in a row.
Limits:
Output
For each test case, print one line of the form "Case #x: y", where x is the case number starting from 1 and y is one of Red, Blue, Neither, or Both. Print Red when only the red player ends up with K pieces in a row, Blue when only the blue player does, Both when both do, and Neither when neither does.