Vārdu meklēšana

ID: vardi
Grūtība: 3/5
Laika limits: 1

Uzdevums

Daudzu avīžu un žurnālu svētdienas numuros tiek publicētas īpaša veida krustvārdu mīklas. Ir dota tabula, kas aizpildīta ar latīņu alfabēta burtiem, un vārdu saraksts. Lai atrisinātu šo mīklu, tabulā jāatrod visi vārdi no dotā saraksta. Meklējamie vārdi tabulā var būt ierakstīti gan pa rindiņām(gan no kreisās puses uz labo, gan no labās puses uz kreiso), gan pa kolonnām(gan no augšas uz leju, gan no lejas uz augšu).
Mīklas atrisinājumu iegūst, ja no tabulas izsvītro burtus, kas veido dotā saraksta vārdus un pēc tam izlasa atlikušos burtus no kreisās puses uz labo pa rindām no augšas uz leju.
Zināms, ka katrs vārds tabulā ir atrodams tikai vienreiz.
Piemēram, no tabulas

IGSCR
TOMPE
TLUTC
ELPPA
VEEXY
IBMIN
LEONO
ORNUS 
izsvītrojot burtus, kas veido vārdus
ACER, APPLE, BELL, IBM, LEO, OLIVETTI, SGI, SONY, SUN, UNIX,
iegūst sekojošu rezultātu:
***C*
*OMP*
**UT*
*****
**E**
*****
*R***
un šīs mīklas atminējums ir vārds COMPUTER.

Uzrakstiet programmu, kas risina šādas krustvārdu mīklas!

 

Ievaddati

Teksta faila vardi.in pirmajā rindā doti divi naturāli skaitļi - burtu tabulas izmēri - garums H (H<=100) un platums W(W<=100), kas atdalīti ar tukšumsimbolu.
Nākošajās H faila rindās katrā atrodas tieši W burti. Faila i+1-ajā rindā dots tabulas i-tās rindas saturs.
Pēc tabulas satura nākošajā rindā dots meklējamo vārdu skaits N (N<=300).
Nākošajās N rindās katrā dots pa vienam meklējamam vārdam.

 

Izvaddati

Teksta faila vardi.out vienīgajā rindā jāizvada mīklas atminējums.

 

Piemērs

vardi.invardi.out
8 5 
IGSCR
TOMPE
TLUTC
ELPPA
VEEXY
IBMIN
LEONO
ORNUS
10
ACER
APPLE
BELL
IBM
LEO
OLIVETTI 
SGI
SONY
SUN
UNIX
COMPUTER

 

Atsauces

Uzdevums izmantots "Baltijas algoritmizācijas skolas" projektā, kas tika organizēts ar "Sorosa fonds-Latvija" atbalstu 1996.gadā.
© 2001-2002 olimps! http://www.lio.lv/olimps/