Problem E: Juego de letras |
Time Limit: 5 seconds |
Description
Seguramente estás familiarizado con el juego de letras que consiste en buscar palabras en un mapa de letras. Las palabras pueden estar en horizontal, vertical o en diagonal. Sin embargo este juego de letras es distinto a los demás, como se puede observar en los siguientes ejemplos:
En este mapa los bordes no son limitantes. Ya que siempre existe una forma de continuar con el anagrama, tal y como se muestran en los ejemplos anteriores donde se ilustran todas las formas en que se puede formar la cadena ‘1234’ o ‘4321’ como lo quieras ver.
Dado un mapa de n x n (2 < n < 501) caracteres alfanuméricos y m (0 < m < 31) palabras a buscar, imprime el valor decimal del número binario de m digitos Bm Bm-1 … B1, donde Bi = 0 (0 < i <= m) si la i-ésima palabra no puede ser encontrada en el anagrama y Bi = 1 en caso contrario. Puedes estar seguro que todas las letras que conforman al mapa y a las palabras a buscar son todas minúsculas.
Input
La entrada consiste de varios casos de prueba. La primera línea de cada caso consiste de los valores de n y m, luego le siguen n líneas con un mapa de n x n caracteres, y al final una lista de m palabras (cada una de ellas en una línea diferente). La entrada termina con un caso m = n = 0, este último caso no debe producir salida alguna.
Output
Por cada caso imprime una línea con el número decimal formado a partir de las palabras que fueron o no encontradas en el anagrama. Lee la descripción para más detalle.
Sample input |
Sample output |
3 4 hol aod num hola mundo nolu cara 0 0 |
7 |
Problemsetter: Gabriel Filiberto López Pérez