Problem Statement |
| | You are given an N x N board with some 1x1 pieces on it. Each piece is colored and there are at most C colors used. Your task is to move the pieces on the board, so that after those moves each existant color will form one connected group.
Moving Pieces
Moves are performed sequentially. Each move consists of choosing one of the pieces and one of the cardinal directions. The piece will move by one cell in that direction and will push other pieces which are in the way in that direction. You cannot move/push any piece outside the board and such moves will be ignored.
Board Generation
First, N and C are randomly chosen, along with P, the probability that a cell contains a piece. If the generated board doesn't require any moves (no pieces, or they are already connected), it is scrapped, and the board generation process repeats (with new values of N, P and C).
Implementation Details
The board will be given as an array of strings where each string describes one row of the board and each character is one cell. '0' means an empty cell and a digit X describes a piece of color X. You should return an array of moves, where each move is formatted as "<row> <column> <direction>" where direction is one of the following : NORTH, SOUTH, EAST, WEST.
Scoring
Your score for an individual test case will be the BEST/YOU. Where YOU is the number of moves returned by your solution and BEST is the lowest number of moves returned by any of the competitors. Any kind of failure (invalid return, exceeding time/memory limit, moves not resulting in connected groups) will result in 0 score for that test. Your total score is simply the sum of scores for every test case.
Score for example tests equals to the number of moves made by your solution.
Visualizer
A visualizer is available for download. |
| |
Definition |
| | | Class: | PieceMover | | Method: | getMoves | | Parameters: | String[] | | Returns: | String[] | | Method signature: | String[] getMoves(String[] board) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The time limit is 10 seconds and the memory limit is 1024M |
| - | A connected group of one color means that any 2 pieces of the same color should be connected (either directly or indirectly) and the connections are maintained using 4 cardinal directions |
| - | Pieces of different colors may touch each other |
| - | It's possible that even if the C colors were choosen, the genereted board will contain fewer colors |
| - | NORTH describes moves to the lower indexed row, SOUTH to higher to indexed row, WEST to lower indexed column and EAST to higher indexed column |
| - | Moves that are ignored are still counted towards your score |
| - | Rows and columns indexing starts with 0 |
| - | There is no code size limit |
| |
Constraints |
| - | Every random variable is chosen with uniform distribution |
| - | P will be between 0.02 and 0.3 |
| - | C will be between 1 and 4 (inclusive) |
| - | N will be between 20 and 100 |
| |
Examples |
| 0) | |
| | | Returns: "N: 27
P: 0.23748338806315303
C: 4
" | |
|
| 1) | |
| | | Returns: "N: 74
P: 0.20357901822286537
C: 1
" | |
|
| 2) | |
| | | Returns: "N: 78
P: 0.1011464630590571
C: 4
" | |
|
| 3) | |
| | | Returns: "N: 41
P: 0.1424764980179026
C: 4
" | |
|
| 4) | |
| | | Returns: "N: 43
P: 0.025045709812754585
C: 4
" | |
|
| 5) | |
| | | Returns: "N: 71
P: 0.0745598336066438
C: 1
" | |
|
| 6) | |
| | | Returns: "N: 80
P: 0.26380740889360854
C: 2
" | |
|
| 7) | |
| | | Returns: "N: 24
P: 0.18945040079480202
C: 4
" | |
|
| 8) | |
| | | Returns: "N: 84
P: 0.05984107722281923
C: 4
" | |
|
| 9) | |
| | | Returns: "N: 87
P: 0.03499919185032477
C: 4
" | |
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.