5. Poriadna výzva

Táto úloha sa dá nahradiť riešením sady conditions_cpp na Liahni (betaliahen.ksp.sk) . Ak chceš, aby ti namiesto bodov za riešenie tejto úlohy boli započítané body získané riešením spomínanej sady, na stránke odovdzaj pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, alebo máte napríklad problémy s načítaním vstupu, napíšte Andrejovi na

Žaba sa po sústredení opäť zastavil doma v Lučenci. Pri obede sa pochválil ako bolo na sústredení super a čo všetko sa deti naučili. Všetci pri stole boli ohromení.

Jedine babka ostala skeptická a pochybovačne odvetila: “Algoritmy, polia, časová zložitosť… Zaujímavé to veci, ale povedz mi Miško, dokážu sa tie vaše decká popasovať aj s nejakým skutočným problémom?”

Žabovi sa začali potiť dlane a potichu uvažoval, na čo môže babka narážať. Ak by chcela šľachtiť kvetiny, tak decká naučil algoritmus na porovnávanie DNA, takže by to malo byť v pohode. A keby chcela robiť vzory na vyšívanie, tak na to spravila jeho spolužiačka ako bakalársku prácu aplikáciu¹. Ale ak to bude niečo iné…

Pri stole nastalo hrobové ticho. Babke po chvíli premýšľania skĺzli oči na noviny a v nich vidí poslednú nevyriešenú osemsmerovku. V tom jej zablysnú oči.

“A povedz mi Miško, dokázali by tie tvoje deti vyriešiť moje osemsmerovky? S niektorými si ozaj neviem dať rady,” pýta sa babka.

Žaba neváhal a prijal babkinu výzvu.

Pre tých, ktorí nie sú úplne oboznámení s touto hrou: Ide o hru, kde dostanete mriežku písmen a niekoľko slov. V mriežke písmen sa snažíte nájsť a vyškrtnúť zadané slová. Ako už názov napovedá, slová sa môžu v mriežke nachádzať vo ôsmich základných smeroch. Po vyškrtaní všetkých slov ostanú niektoré písmená nepreškrtnuté. Keď si ich zapíšete v poradí odhora dole a zľava doprava, dostanete riešenie osemsmerovky. Zväčša je to odpoveď k nejakej hádanke alebo vtipu.

Úloha

Na vstupe dostanete osemsmerovku a zoznam slov, ktoré v nej máte nájsť. Vašou úlohou je nájsť riešenie osemsmerovky, teda písmená, ktoré ostanú po vyškrtaní všetkých týchto slov.

Slovo v osemsmerovke je postupnosť písmen v jednom z ôsmich smerov. Je zaručené, že žiadne slovo sa v osemsmerovke nenachádza viackrát. Slová sa môžu v osemsmerovke prekrývať, avšak platí, že žiadne nie je úplne prekryté iným slovom.

Vstup

Na prvom riadku vstupu dostanete tri čísla: \(r\), \(s\) a \(n\). Číslo \(r\) určuje počet riadkov a číslo \(s\) počet stĺpcov osmesmerovky. \(n\) je počet slov, ktoré je v osemsmerovke treba vyškrtnúť.

Na každom z ďalších \(r\) riadkov je \(s\) znakov, ktoré popisujú samotnú osemsmerovku. Nakoniec je na vstupe \(n\) slov, každé na samostatnom riadku.

Znaky na vstupe predstavujúce osemsmerovku a hľadané slová sú malé písmená anglickej abecedy.

Pri riešení v jazyku C++ vám odporúčame využiť dátovú štruktúru string. K jej použitiu je potrebné na začiatok vášho programu pridať #include<string>. Do stringu potom viete pomocou cin >> načítavať vstup a pracovať s ním ako s poľom, v ktorom je na každej pozícii jeden znak (typ char).

Opäť pripomíname, že ak by ste mali problémy s načítavaním a spracovaním vstupu, či už v C++, Pythone alebo niečom inom, napíšte Andrejovi.

Výstup

Na výstup vypíšte písmená, ktoré ostali po vyškrtaní všetkých slov, v poradí, v akom by ste ich čítali pri klasickej osemsmerovke. Výstup ukončite znakom konca riadku.

Hodnotenie

Vaše riešenie bude hodnotené na viacerých sadách testovacích vstupov. V preklade to znamená, že aj pomalšie korektné riešenia dostanú nejaký počet bodov a teda sa ich oplatí odovzdať.

Vo všetkých sadách bude platiť, že \(r,s \leq 100\) a \(n \leq 40\). Zároveň platí, že celkový súčet dĺžok slov neprekročí \(400\).

V jednotlivých sadách platia nasledujúce obmedzenia:

• V prvej sade platí, že \(r = 1\) a \(n = 1\). Osemsmerovka má teda iba jeden riadok a hľadáte v nej iba jedno slovo.

• V druhej sade platí, že \(r = 1\). Osemsmerovka má iba jeden riadok, hľadáte v nej však viacero slov.

• V tretej sade platí, že \(n = 1\). To znamená, že hoci osemsmerovka môže byť ľubovoľne veľká, vy v nej budete hľadať iba jediné slovo.

• V štvrtej sade platí, že \(r \cdot s \leq 50\). Teda osemsmerovka bude relatívne menšia.

• Pre piatu sadu neplatia žiadne špeciálne obmedzenia.

Za vyriešenie každej z týchto sád získate 3 body.

Príklady

Input:

9 9 15
zapamkacg
kkjadrorn
ioyrylati
askznmaes
stssaiyhu
erttmjpsl
railistrk
dkonkalvy
aaskatsec
adresa
cesta
cyklus
dynamika
gramatika
halda
jadro
jazyk
kostra
list
mapa
mys
skok
tok
vlakno

Output:

zacniriesitprask

Táto osemsmerovka sa nachádzala na letáku PRASKu

Input:

5 4 3
ccxb
xabf
xaxf
xaxf
xaxf
abb
aaaa
cc

Output:

xxfxxfxxfxxf