After solving all other problems, XORin, Lu-chan and Golgo decided to relax with a game of FloodIt.
The game is played on a 14×14 square board. There are 6 available colors, numbered from 0 to 5. Initially, each cell contains exactly one color. Your task is to clear the board (that is, reach a configuration where all 196 cells have exactly the same color).
In order to reach the goal, you can make at most 25 steps. A step is defined as choosing one color and applying a four-way Flood fill algorithm on the top-left corner. All cells reached by the flood fill acquire the color you have chosen.
Input
The input contains the initial configuration of the game, on 14 different lines.
There are 40 tests. You can see the first 39 of them here.
Output
The output should contain a sequence an of no more than 25 integers. Each integer ai represents the color you choose at step i. Your solution will be accepted only if it clears the entire board. It is guaranteed that at least one solution exists.
Sample
| Input | |
|---|---|
| Output | |
| 15254145520131 24303530051050 54411023142542 34124544510531 44340010423531 30454224451500 40335551333131 04313012420550 10114335425520 21133252143100 54400100211055 21524132151352 03145524510153 04533014405330 | 2 4 1 0 3 5 1 3 0 4 5 1 0 5 2 3 1 2 4 0 1 5 |
The first idea that comes to mind is generating all possible sequences of no more than 25 steps. Considering the large number of configurations, we are constrained to limiting the number of steps (e.g. no more than 5) through which we "look ahead" and plan accordingly.
This way, for any board configuration, we want to define the cost of one step, and try to somehow bring it to a minimum.
The notion of a "cost" can be defined in several ways:
- the number of connected components (most important)
- the number of edge cells that are visited
- the number of edges reached (least important)
By merging all three heuristics, we can develop a strategy that is good enough to pass most test cases.
However, there are still some tests where our method exceeds the 25-step limit. In this situation, we keep track of the first 25 steps, choose a random step where we try a different color, and rebuild the configuration from there on. If the sequence is still too long, we go back to the previous step and apply the same idea.
