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 \times 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\ast$ s_2-yə uyğun gəlir.

• Hər bir $A$, $B$, $\dots$, $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.