Sopa de letras P19854

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