Typesetting
Müasir şriftlər əsasən iki növə ayrılır: kontur şriftləri, qlifləri (fərdi simvol formaları) əyri dəstləri kimi riyazi olaraq müəyyənləşdirilən və bitmap şriftləri, qlifləri piksel nümunələri kimi müəyyənləşdirilən. Şriftlər həmçinin kerning cütləri (məsələn, "AW" kimi müəyyən qlif cütləri arasında məsafəni tənzimləmək üçün), izləmə ipuçları (qliflər arası məsafəni idarə etmək üçün), antialiasing ipuçları (piksel kənarlarının hamarlanması) və daha çox daxili məlumatları da ehtiva edə bilər. Müasir şriftlər sadəcə forma kolleksiyasından daha çoxdur və onları düzgün göstərmək ümumi bir proqramlaşdırma problemidir.
Bu problem üçün biz bitmap şriftləri və qlif qablaşdırması adlanan sadə bir tərtibat növü ilə maraqlanacağıq. Əsas məqsəd qlifləri mümkün qədər sıx qablaşdırmaqdır, qliflər arasında ən azı bir üfüqi piksel məsafəsi saxlamaq şərti ilə. Məsələn, aşağıda solda göstərilən Roma simvolları "P" və "J" üçün qlifləri nəzərdən keçirin. Sağdakı şəkil onları qlif qablaşdırmasından sonra göstərir. Qliflər üfüqi olaraq toxunmadan mümkün qədər yaxın yerləşdirilib.
Başqa bir nümunə olaraq, son qlifin ümumiyyətlə qablaşdırıla bilmədiyini qeyd edin.
Qablaşdırmadan sonra, fərqli qliflərdən olan piksellər diaqonal və ya şaquli olaraq bitişik ola bilər, lakin üfüqi olaraq deyil. Aşağıdakı nümunə piksellərin diaqonal olaraq bitişik ola biləcəyini göstərir. Nümunə giriş bölməsindəki "Love" test işi onların şaquli olaraq bitişik ola biləcəyini göstərir.
Qlif qablaşdırması "fancy" qlifləri şriftə daxil etməyi asanlaşdıran bir xüsusiyyətə malikdir, belə ki, heç bir əlavə iş olmadan xüsusi effektlər yaradır. Aşağıdakı "Toy" nümunəsinə baxın. Eyni sadə qablaşdırma prosesi bu qliflərə tətbiq edilmişdir, lakin nəticə daha dramatikdir:
Qlif qablaşdırmasının bir neçə məhdudiyyəti var, lakin bu problem üçün biz birinə diqqət yetirməliyik. Aşağıda solda bir tire qlifi bir alt xətt qlifi ilə izlənildiyi nümunəni nəzərdən keçirin. Üfüqi piksel ayrılığı qaydamıza əsasən, bu necə qablaşdırılacaq? Aydın şəkildə daha çox şey lazımdır və bu daha çox şey qliflərin özlərindəki ipuçlarıdır. Xatırlayın ki, əslində, şriftlər kerning cütləri, izləmə ipuçları və s. ehtiva edir. Bizim məqsədlərimiz üçün ipuçlarımız "görünməz" piksellərlə məhdudlaşacaq ki, bunlar qablaşdırma məqsədi üçün piksel kimi sayılır, lakin göstərilmək üçün deyil. Aşağıdakı mərkəz şəkil görünməz pikselləri qapalı nöqtələr əvəzinə açıq nöqtələr kimi təmsil edir. İndi iki qlif düzgün qablaşdırıla bilər, nəticədə sağda göstərilən çıxış alınır.
İndi düzgün qablaşdırmanın rəsmi tərifi: (1) Qliflər müxtəlif qliflərdən olan piksellərin dərhal üfüqi olaraq bitişik olmasına imkan vermədən mümkün qədər yaxın qablaşdırılır; (2) İki qlif verildikdə, sol qlifin müəyyən bir hündürlükdəki hər hansı bir pikseli sağ qlifin eyni hündürlükdəki hər hansı bir pikselinin sağında yerləşdirilə bilməz.
Yuxarıdakı (2) şərti iki qlifin yan-yana oturduğunu, kiçik bir boşluqla ayrıldığını təsəvvür edərək asanlıqla başa düşülür. Onları "sıxışdırırsınızsa", (2) şərti onların piksellərinin bir-birindən "keçməsinə" icazə verilmədiyini deyir. Aşağıda solda olan nümunəni nəzərdən keçirin. Mərkəz şəkil düzgün qablaşdırma deyil, çünki rəsmi tərifin (2) şərtini pozur. Sağdakı şəkil bu qliflərin düzgün qablaşdırılmasıdır.
Giriş verilənləri
Bu problemin girişi qablaşdırılacaq qlif dəstləridir. Verilən test işində bütün qliflər eyni hündürlükdədir və test işinin ilk sətrindəki N tam ədədi bu hündürlüyü göstərir. Növbəti N sətir qablaşdırılacaq qlifləri ehtiva edir. Qlifdəki boş piksellər nöqtə '.' simvolu ilə təmsil olunur. Görünən piksellər görünən piksellər üçün hash işarəsi '#' və görünməz piksellər üçün sıfır '0' ilə təmsil olunur. Qliflər bir sütun boşluq simvolu ilə ayrılır. Giriş həmişə bir neçə qlifdən ibarət olacaq, bunlardan ən azı biri həmişə ən azı bir görünən piksel ehtiva edəcək. Qlif həmişə sol və sağ sütununda ən azı bir boş olmayan pikselə malik olacaq və hər bir qlif girişdə ən azı bir başqa qliflə eyni hündürlükdə ən azı bir boş olmayan pikselə malik olacaq. Qlifin minimum ölçüsü 1 × 1, maksimum ölçüsü 20 × 20-dir və hər hansı bir test işində görünəcək maksimum qlif sayı 20-dir. Test işləri N üçün sıfır dəyəri təyin olunana qədər davam edir.
Çıxış verilənləri
Hər bir test işi üçün əvvəlcə həmin test işinin nömrəsini (1-dən başlayaraq) ayrıca bir sətirdə çıxarın. Sonra giriş qliflərinin düzgün qablaşdırılmasını çıxarın, boş piksellər və görünməz piksellər üçün nöqtə '.' simvolundan və görünən piksellər üçün hash işarəsi '#' simvolundan istifadə edin. Hər iki tərəfdə ən azı bir görünən piksel ehtiva edən çıxış sütunları ilə belə, boş olan ön və arxa sütunları buraxın.