Word search P19854


Statement
 

pdf   zip

html

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

Public test cases
  • 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
    
  • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++