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