Задача Лойда#4344
Сем Лойд — відомий американський майстер головоломок. Одна з його найвідоміших головоломок — це "Гра в п'ятнадцять". Він також автор багатьох шахових задач і задач на розрізання. Тепер ви можете спробувати розв'язати його задачу про розрізання шахової дошки.
Вам дано шахову дошку розміром n \times n. Потрібно розрізати її на найбільшу кількість частин так, щоб будь-які дві частини були різними. Кожна частина повинна складатися з однієї чи декількох клітинок і являти собою зв'язну по стороні фігуру. Частини, які відрізняються лише поворотом, вважаються однаковими. Наприклад, існує дві одноклітинних частини: чорна клітинка та біла клітинка, і лише одна частина, що складається з двох клітинок.
Ось одне із можливих рішень оригінальної задачі Лойда про розрізання звичайної шахової дошки 8 \times 8 на різних частин:
У першому рядку міститься одне ціле число — довжина сторони дошки (1 \leq n \leq 30).
У першому рядку виведіть максимальну кількість різних частин, на які можна розрізати дошку. Далі виведіть саме розрізання: рядків по малих латинських букв у кожному. Кожна частина повинна складатися з однакових букв. Одну й ту ж букву можна використовувати для позначення декількох частин, але будь-які дві частини, що мають спільну сторону, повинні позначатися різними буквами (див. приклад для пояснення). Якщо існує декілька оптимальних розрізань, дозволяється вивести будь-яке з них.
Приклад 1