Word search P19854
You must solve a word search. ¿does it seem easy? It is, except for a little detail: we are not only going to allow that the words appear in rows, columns or diagonals, but also that “go round”: when the board ends, the word can “continue” in the opposite side. ¿Look the following instance: do you find the word “abracadabra”?
z z a z z a z z d z z r z z b z z c z z a z z a z z r z z a z z b
A detail: we do not accept that the same letter of the word search corresponds to two or more different letters in the word. For instance, the following word search do not contain the word “abracadabra”; instead, it contains the word “zbzzbz” (in diagonal, not in vertical).
z z z z z z z z z z a b r a b r a c a d z z z z z z z z z z
Input A test data contains various cases, separated by a line in white. Each case starts with three naturals separated by spaces, R, C and N. It is fulfilled that 3≤ F, C ≤ 100 and 0≤ N ≤ 100. Then, R lines follow with C lowercase letters each one of them, describing the word search. Finally, N lines, each one of them contains a non empty word formed by lowercase letters that you must search in the word search.
Output Return the same board marking all the appearances of each word. Mark it writing with uppercase letters all the letters that are part of one of the words that you searchs. Consider that the same word can appear many times, once or never in the word search. Separe two cases with a line in white.
Score
- (40 points) Some test data will contain word searchs where any word will appear in diagonal, nor going round the board, as the ones in the instance 1.
- (20 points) Some test data will contain word searchs where any will not be any word that appear in diagonal, as the ones in the instance 2.
- (40 points) Other test data will contain cases of all kinds, as the ones in the instance 3.
Author: Omer Giménez
Input
6 6 2 zzzzzz zabcdz zbcdez zcdefz zdefgz zzzzzz g edcb 4 10 5 asorfliasd iievneivja aramapolaz aifjlalsnd amapola rosa iris nenufar azahar
Output
zzzzzz zaBcdz zBCDEz zcDefz zdEfGz zzzzzz ASORfliasd iIevneivja aRAMAPOLAz aIfjlalsnd
Input
3 3 1 aaa aaa aaa aaaa 10 10 5 ajfmcxzsdf afijalifei afdijfwiwf dafjiljijw afijwliejl adifjvslid ijiljwifwj fvjdlsfsfj ajeijwlijw jilxzvzkqd wajeij jijmxi fsiksfiiel w fvjdlsfsfjf
Output
aaa aaa aaa ajfMcxzSdf afiJaliFei afdIjfWIWf dafJiljIjW afijWliEjl adifjvsLid ijiljWiFWj fvjdlsfSfj AJEIJWlIjW jilXzvzKqd
Input
3 10 1 zzazzazzdzz rzzbzzczzaz zazzrzzazzb abracadabra 3 10 1 zzazzazzdzz rzzbzzczzaz zazzrzzazzb zzzzz 3 9 2 zzzzzzzzzz abrabracad zzzzzzzzzz abracadabra zbzzbz 3 9 1 zzzzzzzzzz abrabracad zzzzzzzzzz zbzzbzzczzazzazzazzd
Output
zzaZZaZzdz zrZZBZZczz azZaZZrzza
- Author
- Omer Giménez
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++ Java