시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 124 92 84 75.000%

문제

은기는 모바일 게임 개발자이다. 이번에 은기가 만드는 게임은 Chain Shot! 게임 (SameGame, Jawbreaker, Bubble Shot, ... 으로도 알려져 있다)을 응용한 "한번 쏘면 멈출 수 없어" 이다.

게임은 직사각형 게임판에서 진행되며, 각 칸에는 색칠된 구슬이 채워져 있다. 플레이어는 각 턴마다 같은 색으로 이루어진 인접한 구슬 그룹을 선택한다. 선택한 구슬은 모두 게임판에서 제거된다. 구슬이 떠있는 경우에는 모두 바닥으로 떨어지게 되고, 빈 열은 제거된다.

각 턴마다 플레이어가 얻는 점수는 그룹을 구성하는 구슬 개수의 제곱이다. 예를 들어, 위의 그림에서 플레이어는 49점을 받게 된다.

게임판에 구슬이 모두 없어지면 게임은 끝나게 되고, 플레이어의 점수는 각 턴마다 얻은 점수의 합이 된다.

레벨의 설계도는 게임판의 크기와 각 구슬 색상의 수로 이루어져 있다.

레벨의 설계도가 주어졌을 때, 설계도로 만들 수 있는 레벨 중 얻을 수 있는 점수가 가장 높은 것을 구하는 프로그램을 작성하시오. 

입력

입력으로 레벨의 설계도가 주어진다.

첫째 줄에는 게임판의 행의 수 h와 열의 수 w, 색상의 수 c가 주어진다. (1 ≤ h, w ≤ 10, 1 ≤ c ≤ 9)

둘째 줄에는 c개의 양의 정수가 주어지며, 각 정수는 그 색상 구슬의 개수이다. 구슬 개수의 합은 h·w가 된다.

출력

만든 h×w 게임판을 출력한다. 첫 번째 색상은 1, 두 번째 색상은 2, ... 로 출력한다.

예제 입력 1

3 5 3
4 4 7

예제 출력 1

31233
12211
33233

힌트

최대 81점을 얻을 수 있다. 

 

W3sicHJvYmxlbV9pZCI6IjM5OTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NWNcdWJjODggXHVjM2Q4XHViYTc0IFx1YmE0OFx1Y2Q5YyBcdWMyMTggXHVjNWM2XHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NDBcdWFlMzBcdWIyOTQgXHViYWE4XHViYzE0XHVjNzdjIFx1YWM4Y1x1Yzc4NCBcdWFjMWNcdWJjMWNcdWM3OTBcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YmM4OFx1YzVkMCBcdWM3NDBcdWFlMzBcdWFjMDAgXHViOWNjXHViNGRjXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBDaGFpbiBTaG90ISBcdWFjOGNcdWM3ODQgKFNhbWVHYW1lLCBKYXdicmVha2VyLCBCdWJibGUgU2hvdCwgLi4uIFx1YzczY1x1Yjg1Y1x1YjNjNCBcdWM1NGNcdWI4MjRcdWM4MzggXHVjNzg4XHViMmU0KVx1Yzc0NCBcdWM3NTFcdWM2YTlcdWQ1NWMgJnF1b3Q7XHVkNTVjXHViYzg4IFx1YzNkOFx1YmE3NCBcdWJhNDhcdWNkOWMgXHVjMjE4IFx1YzVjNlx1YzViNCZxdW90OyBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNWQwXHVjMTFjIFx1YzljNFx1ZDU4OVx1YjQxOFx1YmE3MCwgXHVhYzAxIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWMwYzlcdWNlNjBcdWI0MWMgXHVhZDZjXHVjMmFjXHVjNzc0IFx1Y2M0NFx1YzZjY1x1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCBcdWFjMDEgXHVkMTM0XHViOWM4XHViMmU0IFx1YWMxOVx1Yzc0MCBcdWMwYzlcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWFkNmNcdWMyYWMgXHVhZGY4XHViOGY5XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1Y1x1YjJlNC4gXHVjMTIwXHVkMGRkXHVkNTVjIFx1YWQ2Y1x1YzJhY1x1Yzc0MCBcdWJhYThcdWI0NTAgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNWQwXHVjMTFjIFx1YzgxY1x1YWM3MFx1YjQxY1x1YjJlNC4gXHVhZDZjXHVjMmFjXHVjNzc0IFx1YjVhMFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViYWE4XHViNDUwIFx1YmMxNFx1YjJlNVx1YzczY1x1Yjg1YyBcdWI1YThcdWM1YjRcdWM5YzBcdWFjOGMgXHViNDE4XHVhY2UwLCBcdWJlNDggXHVjNWY0XHVjNzQwIFx1YzgxY1x1YWM3MFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9idWJibGUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTM3cHg7IG9wYWNpdHk6MC45OyB3aWR0aDo2MTlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTM0XHViOWM4XHViMmU0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWM1YmJcdWIyOTQgXHVjODEwXHVjMjE4XHViMjk0IFx1YWRmOFx1YjhmOVx1Yzc0NCBcdWFkNmNcdWMxMzFcdWQ1NThcdWIyOTQgXHVhZDZjXHVjMmFjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWM4MWNcdWFjZjFcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IDQ5XHVjODEwXHVjNzQ0IFx1YmMxYlx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1ZDMxMFx1YzVkMCBcdWFkNmNcdWMyYWNcdWM3NzQgXHViYWE4XHViNDUwIFx1YzVjNlx1YzViNFx1YzljMFx1YmE3NCBcdWFjOGNcdWM3ODRcdWM3NDAgXHViMDVkXHViMDk4XHVhYzhjIFx1YjQxOFx1YWNlMCwgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVjNzU4IFx1YzgxMFx1YzIxOFx1YjI5NCBcdWFjMDEgXHVkMTM0XHViOWM4XHViMmU0IFx1YzViYlx1Yzc0MCBcdWM4MTBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViODA4XHViY2E4XHVjNzU4IFx1YzEyNFx1YWNjNFx1YjNjNFx1YjI5NCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwXHVjNjQwIFx1YWMwMSBcdWFkNmNcdWMyYWMgXHVjMGM5XHVjMGMxXHVjNzU4IFx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI4MDhcdWJjYThcdWM3NTggXHVjMTI0XHVhY2M0XHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzEyNFx1YWNjNFx1YjNjNFx1Yjg1YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWI4MDhcdWJjYTggXHVjOTExIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWI4MDhcdWJjYThcdWM3NTggXHVjMTI0XHVhY2M0XHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NTggXHVkNTg5XHVjNzU4IFx1YzIxOCBoXHVjNjQwIFx1YzVmNFx1Yzc1OCBcdWMyMTggdywgXHVjMGM5XHVjMGMxXHVjNzU4IFx1YzIxOCBjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBoLCB3ICZsZTsgMTAsIDEgJmxlOyBjICZsZTsgOSk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBjXHVhYzFjXHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWFjMDEgXHVjODE1XHVjMjE4XHViMjk0IFx1YWRmOCBcdWMwYzlcdWMwYzEgXHVhZDZjXHVjMmFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC4gXHVhZDZjXHVjMmFjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NDAgaCZtaWRkb3Q7d1x1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViOWNjXHViNGUwIGgmdGltZXM7dyBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzBjOVx1YzBjMVx1Yzc0MCAxLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzBjOVx1YzBjMVx1Yzc0MCAyLCAuLi4gXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjZDVjXHViMzAwIDgxXHVjODEwXHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2J1YmJsZTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTEzcHg7IG9wYWNpdHk6MC45OyB3aWR0aDozNjRweFwiIFwvPjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM5OTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBZGRpY3RpdmUgQnViYmxlcyIsImRlc2NyaXB0aW9uIjoiPHA+QWxpY2UgaXMgYSBtb2JpbGUgZ2FtZSBkZXZlbG9wZXIuIFNoZSB3cml0ZXMgYSBuZXcgcG9ydCBvZiB0aGUgQ2hhaW4gU2hvdCEgZ2FtZSAoYWxzbyBrbm93biBhcyBTYW1lR2FtZSwgSmF3YnJlYWtlciwgQnViYmxlIFNob3QsIGV0YykgY2FsbGVkIEFkZGljdGl2ZSBCdWJibGVzLjxcL3A+XHJcblxyXG48cD5UaGUgZ2FtZSBpcyBwbGF5ZWQgb24gYSByZWN0YW5ndWxhciBib2FyZCBcdWZiMDFsbGVkIHdpdGggY29sb3IgYnViYmxlcy4gT24gZWFjaCB0dXJuIHBsYXllciBzZWxlY3RzIGEgZ3JvdXAgb2YgYWRqYWNlbnQgYnViYmxlcyBvZiB0aGUgc2FtZSBjb2xvci4gU2VsZWN0ZWQgYnViYmxlcyBhcmUgcmVtb3ZlZCBmcm9tIHRoZSBib2FyZC4gQnViYmxlcyB0aGF0IGFyZSBubyBsb25nZXIgc3VwcG9ydGVkIGZhbGwgZG93bi4gSWYgdGhlcmUgYXJlIGVtcHR5IGNvbHVtbnMsIHRoZXkgYXJlIHJlbW92ZWQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYnViYmxlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzN3B4OyB3aWR0aDo2MTlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgbnVtYmVyIG9mIHBvaW50cyBzY29yZWQgYnkgdGhlIG1vdmUgaXMgYSBzcXVhcmUgb2YgdGhlIG51bWJlciBvZiBidWJibGVzIGluIHRoZSBzZWxlY3RlZCBncm91cC4gRm9yIHRoZSBzYW1wbGUgdHVybiBzaG93biBvbiB0aGUgXHVmYjAxZ3VyZSwgNDkgcG9pbnRzIGFyZSBzY29yZWQuPFwvcD5cclxuXHJcbjxwPlR1cm5zIGFyZSByZXBlYXRlZCB1bnRpbCB0aGUgYm9hcmQgaXMgZW1wdHkuIFRoZSB0b3RhbCBudW1iZXIgb2YgcG9pbnRzIGlzIHRoZSBzdW0gb2YgcG9pbnRzIHNjb3JlZCBvbiBlYWNoIHR1cm4uPFwvcD5cclxuXHJcbjxwPlRoZSBibHVlcHJpbnQgb2YgdGhlIGxldmVsIGNvbnNpc3RzIG9mIGJvYXJkIGRpbWVuc2lvbnMgYW5kIHRoZSBudW1iZXIgb2YgYnViYmxlcyBvZiBlYWNoIGNvbG9yLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gaGVscCBBbGljZSB3cml0ZSBhIGJvbnVzIGxldmVsIGdlbmVyYXRvci4gR2l2ZW4gdGhlIGJsdWVwcmludCwgZ2VuZXJhdG9yIG11c3QgcHJvZHVjZSBhIGxldmVsIHRoYXQgYWxsb3dzIGEgc2tpbGxmdWwgcGxheWVyIHRvIHNjb3JlIHRoZSBtYXhpbXVtIHBvc3NpYmxlIG51bWJlciBvZiBwb2ludHMgY29tcGFyZWQgdG8gYWxsIGxldmVscyB3aXRoIHRoZSBzYW1lIGJsdWVwcmludC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBcdWZiMDFsZSBjb250YWlucyB0aGUgYmx1ZXByaW50LjxcL3A+XHJcblxyXG48cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIHRocmVlIHBvc2l0aXZlIGludGVnZXJzIGgsIHcgYW5kIGMgJm1kYXNoOyBudW1iZXIgb2Ygcm93cyBhbmQgY29sdW1ucyBvZiB0aGUgYm9hcmQsIGFuZCB0aGUgbnVtYmVyIG9mIGNvbG9ycyAoMSAmbGU7IGgsIHcgJmxlOyAxMDsgMSAmbGU7IGMgJmxlOyA5KS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIHRoZSBpbnB1dCBcdWZiMDFsZSBjb250YWlucyBjIHBvc2l0aXZlIGludGVnZXIgbnVtYmVycyAmbWRhc2g7IHRoZSBudW1iZXIgb2YgYnViYmxlcyBvZiBlYWNoIGNvbG9yLiBUaGUgdG90YWwgbnVtYmVyIG9mIGJ1YmJsZXMgaXMgaCAmbWlkZG90OyB3LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgZGVzaWduZWQgbGV2ZWwgJm1kYXNoOyBhIGgmdGltZXM7dyBtYXRyaXggb2YgY2hhcmFjdGVycy4gVGhlIGJ1YmJsZXMgb2YgdGhlIFx1ZmIwMXJzdCBjb2xvciBtdXN0IGJlIGRlbm90ZWQgYnkgJmxzcXVvOzEmcnNxdW87LCB0aGUgc2Vjb25kIGNvbG9yICZtZGFzaDsgYnkgJmxzcXVvOzImcnNxdW87LCBldGMuPFwvcD5cclxuIiwiaGludCI6IjxwPkEgc2VxdWVuY2Ugb2YgdHVybnMsIHlpZWxkaW5nIHRoZSBtYXhpbXVtIHBvc3NpYmxlIG51bWJlciBvZiBwb2ludHMgJm1kYXNoOyA4MTo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9idWJibGUyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExM3B4OyB3aWR0aDozNjRweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d