시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 43 20 19 59.375%

문제

스마트폰을 새로 산 준규는 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 색깔이 선택된 횟수를 출력한다.

예제 입력 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

예제 출력 1

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
W3sicHJvYmxlbV9pZCI6IjkzMzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJGbG9vZC1JdCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMmE0XHViOWM4XHVkMmI4XHVkM2YwXHVjNzQ0IFx1YzBjOFx1Yjg1YyBcdWMwYjAgXHVjOTAwXHVhZGRjXHViMjk0Jm5ic3A7Rmxvb2QtaXRcdWM3NzRcdWI3ODAmbmJzcDtcdWM3YWNcdWJjMGNcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YjBiNFx1YjgyNCBcdWJjMWJcdWM1NThcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZsb29kLUl0XHVjNzQwIFx1YzBjMVx1ZDU1OFx1Yzg4Y1x1YzZiMCA0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBOIFggTiBcdWQ1ODlcdWI4MmNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjZTc4XHVjNzQwIDF+Nlx1Yzc1OCA2XHVhYzAwXHVjOWMwIFx1YzBjOVx1YWU1NFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwIFx1YzJkY1x1Yzc5MVx1YzgxMFx1Yzc0MCBcdWM4MWNcdWM3N2MgXHVjNjdjXHVjYWJkJm5ic3A7XHVjNzE3XHVjZTc4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWM3OTFcdWM4MTBcdWJkODBcdWQxMzAgXHVjNzc4XHVjODExXHVkNTVjIDRcdWJjMjlcdWQ1YTUgXHVjOTExIFx1ZDU1Y1x1Y2U3OFx1Yzc1OCBcdWMwYzlcdWM3NDQgXHVhY2U4XHViNzdjIFx1YWUzMFx1Yzg3NCBcdWNlNzhcdWM3NTggXHVjMGM5XHVjNzQ0IFx1YmMxNFx1YWZiOFx1YWNlMCBcdWNkNWNcdWM4ODVcdWM4MDFcdWM3M2NcdWI4NWMgXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc1OCBcdWMwYzlcdWM3NzQgXHVhYzE5XHVjNTQ0XHVjOWMwXHViYTc0IFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwOWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWQ2OWZcdWMyMThcdWI4NWMgXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc1OCBcdWMwYzlcdWM3NDQgXHVhYzE5XHVhYzhjIFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YmFhOVx1YzgwMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvdXBsb2FkXC9pbWFnZXNcL2Zsb29kaXQxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzM3B4OyB3aWR0aDoxNjRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QmbmJzcDtcdWIyZTRcdWM3NGNcdWFjZmMmbmJzcDtcdWFjMTlcdWM3NDAgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzJkY1x1Yzc5MVx1YzgxMFx1YzVkMFx1YzExYyAzXHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YzVlYyBcdWMwYzlcdWM3NDQgXHViYzE0XHVhZmI4XHViYTc0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3VwbG9hZFwvaW1hZ2VzXC9mbG9vZGl0Mi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzFweDsgd2lkdGg6MTY4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNWI0XHVjMTFjLCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjZTc4IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YmU0OFx1YjNjNFx1Yjk3YyBcdWJjZjRcdWM3NzRcdWIyOTQgXHVjMGM5XHVjNzQwIDRcdWM3NzRcdWJiYzBcdWI4NWMgNFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NzQgXHViYzE0XHViMDEwXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC91cGxvYWRcL2ltYWdlc1wvZmxvb2RpdDMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTMzcHg7IHdpZHRoOjE2NnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjOWM0XHVkNTg5XHVkNTU4XHVjNWVjIFx1YmFhOFx1YjRlMCBcdWNlNzhcdWM3NTggXHVjMGM5XHVjNzQ0IFx1ZDFiNVx1Yzc3Y1x1YzJkY1x1ZDBhNFx1YmE3NCBcdWFjOGNcdWM3ODRcdWM3NzQgXHVkMDc0XHViOWFjXHVjNWI0XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViNTRjLCBcdWNkNWNcdWMxOGNcdWQ2OWZcdWMyMThcdWI4NWMgXHVjMGM5XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YzVlYyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkMDc0XHViOWFjXHVjNWI0XHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWImbmJzcDtcdWM5MDRcdWM3NDAmbmJzcDtcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTg5LFx1YzVmNFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LigxJm5ic3A7JmxlOyBOJm5ic3A7JmxlOyAyMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMThcdWFjMDAgXHVjNzg1XHViODI4XHViNDFjXHViMmU0LiAoMX42XHViOWNjIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgMlx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAmbmJzcDtcdWNkOWNcdWI4MjVcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiZuYnNwO1x1YzkwNFx1Yzc0MCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkMDc0XHViOWFjXHVjNWI0XHVkNTYwIFx1YjU0Y1x1YWU0Y1x1YzljMCZuYnNwO1x1YzBjOVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NWMmbmJzcDtcdWQ2OWZcdWMyMTgsJm5ic3A7XHViMmU0XHVjNzRjIFx1YzkwNFx1Yzc1OCBpIFx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNWQwXHVjMTFjIGkgXHVjMGM5XHVhZTU0XHVjNzc0Jm5ic3A7XHVjMTIwXHVkMGRkXHViNDFjJm5ic3A7XHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MzM3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmxvb2QtSXQiLCJkZXNjcmlwdGlvbiI6IjxwPkZsb29kLUl0IGlzIGEgcG9wdWxhciBvbmUgcGxheWVyIGdhbWUgb24gbWFueSBzbWFydCBwaG9uZXMuIFRoZSBwbGF5ZXIgaXMgZ2l2ZW4gYW4gbiAmdGltZXM7IG4gYm9hcmQgb2YgdGlsZXMgd2hlcmUgZWFjaCB0aWxlIGlzIGdpdmVuIG9uZSBvZiA2IGNvbG91cnMgKG51bWJlcmVkIDEmbmRhc2g7NikuIEVhY2ggdGlsZSBpcyBjb25uZWN0ZWQgdG8gdXAgdG8gNCBhZGphY2VudCB0aWxlcyBpbiB0aGUgTm9ydGgsIFNvdXRoLCBFYXN0LCBhbmQgV2VzdCBkaXJlY3Rpb25zLiBBIHRpbGUgaXMgY29ubmVjdGVkIHRvIHRoZSBvcmlnaW4gKHRoZSB0aWxlIGluIHRoZSB1cHBlciBsZWZ0IGNvcm5lcikgaWYgaXQgaGFzIHRoZSBzYW1lIGNvbG91ciBhcyB0aGUgb3JpZ2luIGFuZCB0aGVyZSBpcyBhIHBhdGggdG8gdGhlIG9yaWdpbiBjb25zaXN0aW5nIG9ubHkgb2YgdGlsZXMgb2YgdGhpcyBjb2xvdXIuPFwvcD5cclxuXHJcbjxwPkEgcGxheWVyIG1ha2VzIGEgbW92ZSBieSBjaG9vc2luZyBvbmUgb2YgdGhlIDYgY29sb3Vycy4gQWZ0ZXIgdGhlIGNob2ljZSBpcyBtYWRlLCBhbGwgdGlsZXMgdGhhdCBhcmUgY29ubmVjdGVkIHRvIHRoZSBvcmlnaW4gYXJlIGNoYW5nZWQgdG8gdGhlIGNob3NlbiBjb2xvdXIuIFRoZSBnYW1lIHByb2NlZWRzIHVudGlsIGFsbCB0aWxlcyBoYXZlIHRoZSBzYW1lIGNvbG91ci4gVGhlIGdvYWwgb2YgdGhlIGdhbWUgaXMgdG8gY2hhbmdlIGFsbCB0aGUgdGlsZXMgdG8gdGhlIHNhbWUgY29sb3VyLCBwcmVmZXJhYmx5IHdpdGggdGhlIGZld2VzdCBudW1iZXIgb2YgbW92ZXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPkl0IGhhcyBiZWVuIHByb3ZlbiB0aGF0IFx1ZmIwMW5kaW5nIHRoZSBvcHRpbWFsIG1vdmVzIGlzIGEgdmVyeSBoYXJkIHByb2JsZW0uIEZvciB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIHNpbXVsYXRlIGEgdmVyeSBzaW1wbGUgZ3JlZWR5IHN0cmF0ZWd5IHRvIHNlZSBob3cgd2VsbCBpdCB3b3Jrczo8XC9wPlxyXG5cclxuPHA+Zm9yIGVhY2ggbW92ZSwgY2hvb3NlIHRoZSBjb2xvdXIgdGhhdCB3aWxsIHJlc3VsdCBpbiB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgdGlsZXMgY29ubmVjdGVkIHRvIHRoZSBvcmlnaW47PGJyIFwvPlxyXG5pZiB0aGVyZSBpcyBhIHRpZSwgYnJlYWsgdGllcyBieSBjaG9vc2luZyB0aGUgbG93ZXN0IG51bWJlcmVkIGNvbG91ci48XC9wPlxyXG5cclxuPHA+VG8gaWxsdXN0cmF0ZSB0aGlzLCB3ZSBsb29rIGF0IHRoZSBcdWZiMDFyc3QgdGVzdCBjYXNlIGluIHRoZSBzYW1wbGUgaW5wdXQsIHRoZSBvcmlnaW5hbCBib2FyZCBpczo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mbG9vZGl0MS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzNweDsgd2lkdGg6MTY0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+SWYgd2UgY2hvb3NlIGNvbG91ciAzIGZvciB0aGUgXHVmYjAxcnN0IG1vdmUsIHRoZSByZXN1bHQgd2lsbCBiZTo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mbG9vZGl0Mi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzFweDsgd2lkdGg6MTY4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+d2hlcmUgdGhlIHRpbGVzIGNvbm5lY3RlZCB0byB0aGUgb3JpZ2luIGFyZSBzaGFkZWQuIEluIHRoZSBuZXh0IG1vdmUsIHdlIGNob29zZSBjb2xvdXIgNCBiZWNhdXNlIHdlIGNhbiBpbmNyZWFzZSB0aGUgbnVtYmVyIG9mIHRpbGVzIGNvbm5lY3RlZCB0byB0aGUgb3JpZ2luIGJ5IDUgdGlsZXM6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZmxvb2RpdDMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTMzcHg7IHdpZHRoOjE2NnB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgbXVsdGlwbGUgdGVzdCBjYXNlcy4gVGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGlzIGEgc2luZ2xlIGludGVnZXIsIG5vdCBtb3JlIHRoYW4gMjAsIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRvIGZvbGxvdy4gRWFjaCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHRoZSBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMjApLiBUaGUgbmV4dCBuIGxpbmVzIGVhY2ggY29udGFpbnMgbiBjaGFyYWN0ZXJzLCBnaXZpbmcgdGhlIGluaXRpYWwgY29sb3VycyBvZiB0aGUgbiAmdGltZXM7IG4gYm9hcmQgb2YgdGlsZXMuIEVhY2ggY29sb3VyIGlzIHNwZWNpXHVmYjAxZWQgYnkgYSBkaWdpdCBmcm9tIDEgdG8gNi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBjYXNlLCBkaXNwbGF5IHR3byBsaW5lcyBvZiBvdXRwdXQuIFRoZSBcdWZiMDFyc3QgbGluZSBzcGVjaVx1ZmIwMWVzIHRoZSBudW1iZXIgb2YgbW92ZXMgbmVlZGVkIHRvIGNoYW5nZSBhbGwgdGhlIHRpbGVzIHRvIHRoZSBzYW1lIGNvbG91ci4gVGhlIHNlY29uZCBsaW5lIHNwZWNpXHVmYjAxZXMgNiBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSBpdGggaW50ZWdlciBnaXZlcyB0aGUgbnVtYmVyIG9mIHRpbWVzIGNvbG91ciBpIGlzIGNob3NlbiBhcyBhIG1vdmUgaW4gdGhlIGdhbWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d