| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
ACM_0080 - FLOOD-IT |
Flood-It is a popular one player game on many smart phones. The player is given an n × n board of tiles where each tile is given one of 6 colours (numbered 1–6). Each tile is connected to up to 4 adjacent tiles in the North, South, East, and West directions. A tile is connected to the origin (the tile in the upper left corner) if it has the same colour as the origin and there is a path to the origin consisting only of tiles of this colour.
A player makes a move by choosing one of the 6 colours. After the choice is made, all tiles that are connected to the origin are changed to the chosen colour. The game proceeds until all tiles have the same colour. The goal of the game is to change all the tiles to the same colour, preferably with the fewest number of moves possible.
It has been proven that finding the optimal moves is a very hard problem. For this problem, you will simulate a very simple greedy strategy to see how well it works:
- for each move, choose the colour that will result in the largest number of tiles connected to the origin;
- if there is a tie, break ties by choosing the lowest numbered colour.
To illustrate this, we look at the first test case in the sample input, the original board is:
|
1 |
2 |
3 |
4 |
2 |
3 |
|
3 |
3 |
4 |
5 |
2 |
1 |
|
4 |
3 |
3 |
1 |
2 |
3 |
|
5 |
4 |
3 |
6 |
2 |
1 |
|
3 |
2 |
4 |
3 |
4 |
3 |
|
2 |
3 |
4 |
1 |
5 |
6 |
If we choose colour 3 for the first move, the result will be:
|
3 |
2 |
3 |
4 |
2 |
3 |
|
3 |
3 |
4 |
5 |
2 |
1 |
|
4 |
3 |
3 |
1 |
2 |
3 |
|
5 |
4 |
3 |
6 |
2 |
1 |
|
3 |
2 |
4 |
3 |
4 |
3 |
|
2 |
3 |
4 |
1 |
5 |
6 |
where the tiles connected to the origin are shaded. In the next move, we choose colour 4 because we can increase the number of tiles connected to the origin by 5 tiles:
|
4 |
2 |
3 |
4 |
2 |
3 |
|
4 |
4 |
4 |
5 |
2 |
1 |
|
4 |
4 |
4 |
1 |
2 |
3 |
|
5 |
4 |
4 |
6 |
2 |
1 |
|
3 |
2 |
4 |
3 |
4 |
3 |
|
2 |
3 |
4 |
1 |
5 |
6 |
Input
The input consists of multiple test cases. The first line of input is a single integer, not more than 20, indicating the number of test cases to follow. Each case starts with a line containing the integer n (1 ≤ n ≤ 20). The next n lines each contains n characters, giving the initial colours of the n × n board of tiles. Each colour is specified by a digit from 1 to 6.
Output
For each case, display two lines of output. The first line specifies the number of moves needed to change all the tiles to the same colour. The second line specifies 6 integers separated by a single space. The ith integer gives the number of times colour i is chosen as a move in the game.
Examples
|
№ |
stdin |
stdout |
|
1 |
4 6 123423 334521 433123 543621 324343 234156 5 12121 21212 12121 21212 12121 5 12345 12345 12345 12345 12345 5 11131 12211 31311 21111 11111 |
12 2 2 4 2 1 1 8 4 4 0 0 0 0 4 4 0 1 1 1 1 0 4 1 2 1 0 0 0 |
| Ավելացրեց. | Հրանտ Հովհաննիսյան |
| Ամսաթիվ. | 2014-01-08 |
| Ժամանակի սահմանափակումը. | 1s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE |
| Աղբյուրը. | NA Rocky Mountain 2013.I |
RSS