|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||128 MB||60||28||25||58.140%|
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 ﬁnding 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 ﬁrst test case in the sample input, the original board is:
If we choose colour 3 for the ﬁrst move, the result will be:
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:
The input consists of multiple test cases. The ﬁrst 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 speciﬁed by a digit from 1 to 6.
For each case, display two lines of output. The ﬁrst line speciﬁes the number of moves needed to change all the tiles to the same colour. The second line speciﬁes 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.
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 0 1 1 1 1 0 4 1 2 1 0 0 0