Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

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:

  1. for each move, choose the colour that will result in the largest number of tiles connected to the origin;
  2. 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 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.NA Rocky Mountain 2013.I

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.