C(O|W|A*RD*|S)* KROSSVORD Tapmacası
İlk krossvord 21 dekabr 1913-cü ildə Artur Vinn tərəfindən nəşr edilmişdir. Onun əmisi babasının ixtirasının yüz illiyini qeyd etmək məqsədilə, Con "Qorxaq" Vinn-1 krossvordlar hazırlamağa çalışırdı. O, o qədər qorxaq idi ki, hər dəfə bir söz üçün ağıllı bir ipucu düşündüyündə, insanların onun pis seçiminə görə onu günahlandıracağından narahat olurdu. Günün sonunda o, nəhayət, tapmacalarını daha az maraqlı edən darıxdırıcı ipuçları seçdi.
Bir gün onun ağlına parlaq bir fikir gəldi: sözlərin mənasının əhəmiyyət kəsb etmədiyi, lakin hələ də maraqlı olan bir tapmaca yaratmaq. O, bu ideyanı həmkarlarına danışdı və onlar bunu kifayət qədər maraqlı hesab etdilər. Hətta onun tapmacalarını ləqəbinə uyğun olaraq "Qorxaq Krossvordları" adlandırdılar.
Lakin Qorxaq krossvordu hazırlamaq asan deyildi. Sözlərin mənaları haqqında düşünməmək lazım olsa da, tapmacanın yalnız bir cavab dəstinə malik olub-olmadığını yoxlamaq asan deyildi. Yüz illik yubiley günü yaxınlaşdıqca, Con vaxtında maraqlı bir şey yarada biləcəyindən narahat olmağa başladı. Gəlin Cona Qorxaq krossvordlarını həll edən bir proqram yazmağa kömək edək.
Hər bir tapmaca h × w hüceyrələrdən ibarətdir, h üfüqi açar və w şaquli açarları ehtiva edir. Açarlar (clue) aşağıdakı BNF sintaksisi ilə müəyyən edilən dildə yazılmış müntəzəm ifadələrdir.
Cədvəl 1. BNF dilinin sintaksisi.
Açarlar (aşağıda p və q ilə göstərilir) aşağıdakı qaydalara uyğun olaraq sözlərə (aşağıda s ilə göstərilir) uyğun gəlir.
^p$ s-ə uyğun gəlir əgər p s-ə uyğun gəlirsə.
p|q s sətrinə uyğun gəlir əgər p və/yaxud q s-ə uyğun gəlirsə.
pq s sətrinə uyğun gəlir əgər elə s_1 və s_2 var ki, s_1s_2 = s, p s_1-ə uyğun gəlir və q s_2-yə uyğun gəlir.
p* s sətrinə uyğun gəlir əgər s boşdursa, və ya elə s_1 və s_2 var ki, s_1s_2 = s, p s_{1 }-ə uyğun gəlir və p* s_2-yə uyğun gəlir.
Hər bir A, B, ..., Z simvolu öz hərfinə uyğun gəlir.
(p) s-ə uyğun gəlir əgər p s-ə uyğun gəlirsə.
. (A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z) qısaltmasıdır.
Aşağıda cavabları hüceyrələrə doldurulmuş bir Qorxaq krossvordu nümunəsi verilmişdir.
Java Xüsusi: Təqdim olunan Java proqramları java.util.regex paketindəki siniflərdən istifadə edə bilməz.
C++ Xüsusi: Təqdim olunan C++ proqramları std::regex sinifindən istifadə edə bilməz.
_________________
^1Bu problemdə iştirak edən bütün personajlar, Artur Vinn istisna olmaqla, uydurmadır. Hər hansı bir real şəxslə, yaşayan və ya ölü, hər hansı bir bənzərlik tamamilə təsadüfidir.
Giriş verilənləri
Giriş bir neçə datasetdən ibarətdir, hər biri aşağıdakı formatda verilmiş bir tapmacanı təmsil edir.
h w
p_1
p_2
...
p_h
q_1
q_2
...
q_w
Burada, h və w müvafiq olaraq şaquli və üfüqi hüceyrələrin sayını təmsil edir, burada 2 ≤ h, w ≤ 4. p_i və q_j müvafiq olaraq i-ci sətir və j-ci sütun üçün üfüqi və şaquli ipuçlarıdır. Hər hansı bir ipucu ən çox 512 simvola malikdir.
Son dataset iki sıfırdan ibarət bir sətirlə tamamlanır. Girişdə ən çox 30 dataset olduğunu qəbul edə bilərsiniz.
Çıxış verilənləri
Hər dataset üçün, tapmaca unikal cavab dəstinə malik olduqda, onu h sətir və w simvol kimi çıxarın. Tapmaca cavab dəstinə malik olmadıqda və ya bir neçə cavab dəstinə malik olduqda, müvafiq olaraq, ikiqat sitat olmadan "none" və ya "ambiguous" çıxarın.