시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMsIFx1Y2Q1Y1x1YzE4Y1x1ZDY5Zlx1YzIxOFx1Yjg1YyBcdWMwYzlcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHVjNWVjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQwNzRcdWI5YWNcdWM1YjRcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiZuYnNwO1x1YzkwNFx1Yzc0MCZuYnNwO1x1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1ODksXHVjNWY0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuKDEmbmJzcDsmbGU7IE4mbmJzcDsmbGU7IDIwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzA4IFx1YzIxOFx1YWMwMCBcdWM3ODVcdWI4MjhcdWI0MWNcdWIyZTQuICgxfjZcdWI5Y2MgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0Lik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCAyXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCZuYnNwO1x1Y2Q5Y1x1YjgyNVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiJm5ic3A7XHVjOTA0XHVjNzQwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQwNzRcdWI5YWNcdWM1YjRcdWQ1NjAgXHViNTRjXHVhZTRjXHVjOWMwJm5ic3A7XHVjMGM5XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1YyZuYnNwO1x1ZDY5Zlx1YzIxOCwmbmJzcDtcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNzU4IGkgXHViYzg4XHVjOWY4IFx1YzIxOFx1YjI5NCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM1ZDBcdWMxMWMgaSBcdWMwYzlcdWFlNTRcdWM3NzQmbmJzcDtcdWMxMjBcdWQwZGRcdWI0MWMmbmJzcDtcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkzMzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGbG9vZC1JdCIsImRlc2NyaXB0aW9uIjoiPHA+Rmxvb2QtSXQgaXMgYSBwb3B1bGFyIG9uZSBwbGF5ZXIgZ2FtZSBvbiBtYW55IHNtYXJ0IHBob25lcy4gVGhlIHBsYXllciBpcyBnaXZlbiBhbiBuICZ0aW1lczsgbiBib2FyZCBvZiB0aWxlcyB3aGVyZSBlYWNoIHRpbGUgaXMgZ2l2ZW4gb25lIG9mIDYgY29sb3VycyAobnVtYmVyZWQgMSZuZGFzaDs2KS4gRWFjaCB0aWxlIGlzIGNvbm5lY3RlZCB0byB1cCB0byA0IGFkamFjZW50IHRpbGVzIGluIHRoZSBOb3J0aCwgU291dGgsIEVhc3QsIGFuZCBXZXN0IGRpcmVjdGlvbnMuIEEgdGlsZSBpcyBjb25uZWN0ZWQgdG8gdGhlIG9yaWdpbiAodGhlIHRpbGUgaW4gdGhlIHVwcGVyIGxlZnQgY29ybmVyKSBpZiBpdCBoYXMgdGhlIHNhbWUgY29sb3VyIGFzIHRoZSBvcmlnaW4gYW5kIHRoZXJlIGlzIGEgcGF0aCB0byB0aGUgb3JpZ2luIGNvbnNpc3Rpbmcgb25seSBvZiB0aWxlcyBvZiB0aGlzIGNvbG91ci48XC9wPlxyXG5cclxuPHA+QSBwbGF5ZXIgbWFrZXMgYSBtb3ZlIGJ5IGNob29zaW5nIG9uZSBvZiB0aGUgNiBjb2xvdXJzLiBBZnRlciB0aGUgY2hvaWNlIGlzIG1hZGUsIGFsbCB0aWxlcyB0aGF0IGFyZSBjb25uZWN0ZWQgdG8gdGhlIG9yaWdpbiBhcmUgY2hhbmdlZCB0byB0aGUgY2hvc2VuIGNvbG91ci4gVGhlIGdhbWUgcHJvY2VlZHMgdW50aWwgYWxsIHRpbGVzIGhhdmUgdGhlIHNhbWUgY29sb3VyLiBUaGUgZ29hbCBvZiB0aGUgZ2FtZSBpcyB0byBjaGFuZ2UgYWxsIHRoZSB0aWxlcyB0byB0aGUgc2FtZSBjb2xvdXIsIHByZWZlcmFibHkgd2l0aCB0aGUgZmV3ZXN0IG51bWJlciBvZiBtb3ZlcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+SXQgaGFzIGJlZW4gcHJvdmVuIHRoYXQgXHVmYjAxbmRpbmcgdGhlIG9wdGltYWwgbW92ZXMgaXMgYSB2ZXJ5IGhhcmQgcHJvYmxlbS4gRm9yIHRoaXMgcHJvYmxlbSwgeW91IHdpbGwgc2ltdWxhdGUgYSB2ZXJ5IHNpbXBsZSBncmVlZHkgc3RyYXRlZ3kgdG8gc2VlIGhvdyB3ZWxsIGl0IHdvcmtzOjxcL3A+XHJcblxyXG48cD5mb3IgZWFjaCBtb3ZlLCBjaG9vc2UgdGhlIGNvbG91ciB0aGF0IHdpbGwgcmVzdWx0IGluIHRoZSBsYXJnZXN0IG51bWJlciBvZiB0aWxlcyBjb25uZWN0ZWQgdG8gdGhlIG9yaWdpbjs8YnIgXC8+XHJcbmlmIHRoZXJlIGlzIGEgdGllLCBicmVhayB0aWVzIGJ5IGNob29zaW5nIHRoZSBsb3dlc3QgbnVtYmVyZWQgY29sb3VyLjxcL3A+XHJcblxyXG48cD5UbyBpbGx1c3RyYXRlIHRoaXMsIHdlIGxvb2sgYXQgdGhlIFx1ZmIwMXJzdCB0ZXN0IGNhc2UgaW4gdGhlIHNhbXBsZSBpbnB1dCwgdGhlIG9yaWdpbmFsIGJvYXJkIGlzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Zsb29kaXQxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzM3B4OyB3aWR0aDoxNjRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JZiB3ZSBjaG9vc2UgY29sb3VyIDMgZm9yIHRoZSBcdWZiMDFyc3QgbW92ZSwgdGhlIHJlc3VsdCB3aWxsIGJlOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Zsb29kaXQyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzMXB4OyB3aWR0aDoxNjhweFwiIFwvPjxcL3A+XHJcblxyXG48cD53aGVyZSB0aGUgdGlsZXMgY29ubmVjdGVkIHRvIHRoZSBvcmlnaW4gYXJlIHNoYWRlZC4gSW4gdGhlIG5leHQgbW92ZSwgd2UgY2hvb3NlIGNvbG91ciA0IGJlY2F1c2Ugd2UgY2FuIGluY3JlYXNlIHRoZSBudW1iZXIgb2YgdGlsZXMgY29ubmVjdGVkIHRvIHRoZSBvcmlnaW4gYnkgNSB0aWxlczo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mbG9vZGl0My5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzNweDsgd2lkdGg6MTY2cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgaXMgYSBzaW5nbGUgaW50ZWdlciwgbm90IG1vcmUgdGhhbiAyMCwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdG8gZm9sbG93LiBFYWNoIGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdGhlIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAyMCkuIFRoZSBuZXh0IG4gbGluZXMgZWFjaCBjb250YWlucyBuIGNoYXJhY3RlcnMsIGdpdmluZyB0aGUgaW5pdGlhbCBjb2xvdXJzIG9mIHRoZSBuICZ0aW1lczsgbiBib2FyZCBvZiB0aWxlcy4gRWFjaCBjb2xvdXIgaXMgc3BlY2lcdWZiMDFlZCBieSBhIGRpZ2l0IGZyb20gMSB0byA2LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGNhc2UsIGRpc3BsYXkgdHdvIGxpbmVzIG9mIG91dHB1dC4gVGhlIFx1ZmIwMXJzdCBsaW5lIHNwZWNpXHVmYjAxZXMgdGhlIG51bWJlciBvZiBtb3ZlcyBuZWVkZWQgdG8gY2hhbmdlIGFsbCB0aGUgdGlsZXMgdG8gdGhlIHNhbWUgY29sb3VyLiBUaGUgc2Vjb25kIGxpbmUgc3BlY2lcdWZiMDFlcyA2IGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIGl0aCBpbnRlZ2VyIGdpdmVzIHRoZSBudW1iZXIgb2YgdGltZXMgY29sb3VyIGkgaXMgY2hvc2VuIGFzIGEgbW92ZSBpbiB0aGUgZ2FtZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=