Набір тексту
Сучасні шрифти зазвичай поділяються на два типи: контурні шрифти, де гліфи (окремі форми символів) визначаються математично як набір кривих, та растрові шрифти, де гліфи представлені як шаблони пікселів. Шрифти також можуть містити вбудовану інформацію, таку як пари кернінгу (регулювання відстані між певними парами гліфів, наприклад, "AW", щоб вони виглядали правильно розташованими), підказки трекінгу (для управління міжгліфовим інтервалом), підказки згладжування (згладжування піксельованих країв) та багато іншого. Безумовно, сучасні шрифти — це більше, ніж просто колекція форм, і їх правильне відображення є поширеною програмною задачею.
У цій задачі ми зосередимося на растрових шрифтах та простій формі верстки, яка називається пакуванням гліфів. Ідея полягає в тому, щоб розміщувати гліфи якомога щільніше, зберігаючи принаймні один горизонтальний піксель відстані між ними. Наприклад, розгляньте гліфи, показані ліворуч нижче для римських символів "P" та "J". Фігура праворуч демонструє їх після пакування. Зверніть увагу, що вони розташовані якомога ближче, не торкаючись горизонтально.
Ось ще один приклад. У цьому випадку зверніть увагу, що останній гліф взагалі не можна упакувати.
Після пакування пікселі з різних гліфів можуть бути суміжними по діагоналі або вертикально, але не горизонтально. Наступний приклад показує, що пікселі можуть бути суміжними по діагоналі. Тестовий випадок "Love" у розділі прикладів вхідних даних демонструє, що вони можуть бути суміжними вертикально.
Пакування гліфів має приємну властивість, що дозволяє легко вбудовувати "фантазійні" гліфи в шрифт, так що пакування гліфів створює спеціальні ефекти без додаткової роботи. Подивіться на приклад "Toy" нижче. До цих гліфів застосовано той самий простий процес пакування, що й до попередніх, але результат є більш драматичним:
Пакування гліфів має кілька застережень, одна з яких нас повинна турбувати в цій задачі. Розгляньте приклад ліворуч нижче, де гліф для дефіса слідує за гліфом для підкреслення. Виходячи з нашого правила одного горизонтального пікселя відстані, як це буде упаковано? Очевидно, що потрібно щось більше, і це щось більше — підказки всередині самих гліфів. Нагадаємо, що на практиці шрифти містять пари кернінгу, підказки трекінгу тощо. Для наших цілей наші підказки будуть обмежені "невидимими" пікселями, які рахуються як піксель для цілей пакування, але не для відображення. Центральне зображення нижче представляє невидимі пікселі як відкриті точки замість закритих точок. Тепер два гліфи можуть бути правильно упаковані, що призводить до виходу, показаного праворуч.
Тепер формальне визначення правильного пакування: (1) Гліфи пакуються якомога ближче, не допускаючи, щоб будь-які пікселі з різних гліфів були безпосередньо горизонтально суміжними; (2) Дано два гліфи, вони не можуть бути упаковані таким чином, щоб будь-який піксель лівого гліфа на заданій висоті опинився правіше будь-якого пікселя на тій самій висоті в правому гліфі.
Умова (2) вище легко зрозуміти, уявивши два гліфи, що стоять поруч, розділені невеликим простором. Якщо ви "стиснете" їх разом, умова (2) говорить, що їх пікселі не можуть "проходити крізь" один одного. Розгляньте приклад ліворуч нижче. Центральне зображення не є правильним пакуванням, оскільки воно порушує умову (2) формального визначення. Зображення праворуч є правильним пакуванням цих гліфів.
Вхідні дані
Вхідні дані для цієї задачі — це набори гліфів, які потрібно упакувати. У даному тестовому випадку всі гліфи мають однакову висоту, і ціле число N на першому рядку тестового випадку вказує цю висоту. Наступні N рядків містять гліфи, які потрібно упакувати. Порожні пікселі в гліфі представлені символом крапки '.', а непорожні пікселі представлені символом решітки '#' для видимих пікселів і нулем '0' для невидимих пікселів. Гліфи розділені одним стовпцем пробілів. Вхід завжди складається з більш ніж одного гліфа, принаймні один з яких завжди міститиме принаймні один видимий піксель. Гліф завжди матиме принаймні один непорожній піксель у своєму лівому та правому стовпцях, і кожен гліф матиме принаймні один непорожній піксель на тій самій висоті, що й принаймні один інший гліф у вхідних даних. Мінімальний розмір гліфа — 1 × 1, максимальний розмір — 20 × 20, а максимальна кількість гліфів, які можуть з'явитися в будь-якому тестовому випадку, — 20. Тестові випадки продовжуються, поки для N не буде вказано значення нуль.
Вихідні дані
Для кожного тестового випадку спочатку виведіть номер цього тестового випадку (починаючи з 1) на окремому рядку. Потім виведіть правильне пакування вхідних гліфів, використовуючи символ крапки '.' для порожніх пікселів і для невидимих пікселів, а символ решітки '#' для видимих пікселів. Пропустіть початкові та кінцеві порожні стовпці (стовпці без видимих пікселів), щоб як лівий, так і правий вихідні стовпці містили принаймні один видимий піксель.