시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 34 19 18 58.065%

문제

스마트폰을 새로 산 준규는 Flood-it이란 재밌는 게임을 내려 받았다. 

Flood-It은 상하좌우 4방향으로 인접한 N X N 행렬이 주어진다. 각 칸은 1~6의 6가지 색깔로 이루어져 있고 시작점은 제일 왼쪽 윗칸이다.

시작점부터 인접한 4방향 중 한칸의 색을 골라 기존 칸의 색을 바꾸고 최종적으로 모든 칸의 색이 같아지면 게임이 끝난다. 이때, 가장 적은 횟수로 모든 칸의 색을 같게 하는 것이 게임의 목적이다.

만약 다음과 같은 게임판이 주어졌을 때, 시작점에서 3을 선택하여 색을 바꾸면 다음과 같다.

이어서, 인접한 칸 중 가장 많은 빈도를 보이는 색은 4이므로 4를 선택하면 다음과 같이 게임판이 바뀐다.

이와 같이 진행하여 모든 칸의 색을 통일시키면 게임이 클리어된다.

이 때, 최소횟수로 색을 선택하여 게임을 클리어하는 경우를 출력한다.

입력

첫 줄은 테스트 케이스가 주어진다. 

각 테스트 케이스는 행,열을 나타내는 정수 N이 주어진다.(1 ≤ N ≤ 20)

다음 N줄에는 게임판에 들어갈 수가 입련된다. (1~6만 들어온다.)

출력

각 테스트 케이스는 2줄에 걸쳐 출력된다.

첫 줄은 게임을 클리어할 때까지 색을 선택한 횟수, 다음 줄의 i 번째 수는 게임판에서 i 색깔이 선택된 횟수를 출력한다.

예제 입력

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

힌트