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