Sopa de letras P19854


Statement
 

pdf   zip

html

Deberás resolver una sopa de letras. ¿Parece sencillo? Lo es, excepto por un pequeño detalle: no sólo vamos a permitir que las palabras aparezcan por filas, columnas o diagonales, sino también que “den la vuelta”: cuando se acaba el tablero, la palabra puede “continuar” por el lado opuesto. ¿Mejor mira el siguiente ejemplo: encuentras la palabra “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

Un detalle: no aceptamos que la misma letra de la sopa de letras se corresponda con dos o más letras distintas en la palabra. Por ejemplo, la siguiente sopa de letras no contiene la palabra “abracadabra”; en cambio, si contiene la palabra “zbzzbz” (en diagonal, no en 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

Entrada Un juego de pruebas contiene varios casos, separados entre sí por una línea en blanco. Cada caso empieza con tres naturales separados por espacios, F, C y N. Se cumple 3≤ F, C ≤ 100 y 0≤ N ≤ 100. A continuación siguen F líneas con C letras minúsculas cada una de ellas, describiendo la sopa de letras. Finalmente, N líneas, cada una de las cuales contiene una palabra no vacía formada por letras minúsculas que deberás buscar en la sopa de letras.

Salida Devuelve el mismo tablero marcando todas las apariciones de cada una de las palabras. Márcalo escribiendo en mayúsculas todas aquellas letras que formen parte de una de las palabras que buscas. Ten en cuenta que la misma palabra puede aparecer varias, una o ninguna vez en la sopa. Separa dos casos con una línea en blanco.

Puntuación

  • (40 puntos) Algunos juegos de pruebas contendrán sopas de letras donde ninguna palabra aparecerá ni en diagonal ni dando la vuelta al tablero, como las del ejemplo 1.
  • (20 puntos) Algunos juegos de pruebas contendrán sopas de letras donde no habrá ninguna palabra que aparezca en diagonal, como las del ejemplo 2.
  • (40 puntos) Otros juegos de pruebas tendrán casos de todo tipo, como los del ejemplo 3.

Autor: 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
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++ Java