Teclado de televisor
Queremos buscar series y películas en la televisión de la forma más eficiente posible. Cuando se busca un texto en la televisión aparece un teclado virtual por el que nos desplazamos con las flechas del mando a distancia: arriba, derecha, abajo e izquierda. El objetivo es calcular el número mínimo de desplazamientos que hay que realizar dado un teclado y un texto a introducir determinados. Debe tenerse en cuenta que hay teclas de distinto tamaño y que se trata de un teclado circular: cuando el cursor se sale por un extremo del teclado, aparece por el extremo opuesto. El cursor se situa inicialmente sobre la tecla que ocupa la esquina superior izquierda.
A continuación se muestra un ejemplo de teclado:
AAABCD
AAAGHI
LEEEEK
Un teclado tiene forma rectangular, y todas sus teclas son también rectángulos, aunque puede haber teclas de diferentes tamaños. Así, en el teclado del ejemplo la tecla A tiene dimensiones 2 × 3, la tecla B tiene dimensiones 1 × 1, la E 1 × 4, etc. El efecto de pulsar cada una de las flechas del mando a distancia se describe a continuación:
- Derecha: el cursor se desplaza a la tecla de la derecha, y si hay varias a la de más arriba. En el ejemplo, si se pulsa derecha cuando el cursor está sobre la tecla A, el cursor se situará sobre la tecla B.
- Izquierda: el cursor se desplaza a la tecla de la izquierda, y si hay varias a la de más arriba. En el ejemplo, si se pulsa izquierda cuando el cursor está sobre la tecla A, el cursor se situará sobre la tecla D.
- Arriba: el cursor se desplaza a la tecla de arriba, y si hay varias a la de más a la izquierda. En el ejemplo, si se pulsa arriba cuando el cursor está sobre la tecla E, el cursor se situará sobre la tecla A.
- Abajo: el cursor se desplaza a la tecla de debajo, y si hay varias a la de más a la izquierda. En el ejemplo, si se pulsa abajo cuando el cursor está sobre la tecla A, el cursor se situará sobre la tecla L.
Para el teclado del ejemplo, una posible forma de teclar el texto ADKEAB con el mínimo número de desplazamientos podría ser: izquierda, arriba, izquierda, arriba y derecha.
Entrada
La entrada está formada por la descripción de una serie de teclados, y hay varios textos de prueba para cada teclado. La descripción de un teclado empieza con una línea con tres números enteros: F, el número de filas del teclado; C, el número de columnas; y N, el número de textos a introducir usando el teclado. Se garantiza que 1 ≤ F ≤ 8, 1 ≤ C ≤ 20 y 1 ≤ N ≤ 100. A continuación aparecen F líneas, con C caracteres cada una, describiendo el teclado según el formato del ejemplo anterior. Los caracteres válidos son las letras mayúsculas y los números, además del punto ("."), que representa el espacio. Las teclas son siempre rectangulares y nunca hay dos teclas distintas asociadas al mismo carácter.
Tras la descripción del teclado aparecen N líneas, cada una con una cadena de texto a introducir usando el teclado. Todas las cadenas están formadas con los caracteres asociados a las teclas del teclado, y nunca tienen una longitud mayor que 100. Al empezar a escribir cada palabra, el cursor está en la letra superior izquierda del teclado, independientemente de dónde terminara con la anterior.
El final de la entrada se indica con una línea con tres ceros que no se debe procesar.
Salida
Para cada texto de prueba se debe imprimir, en una línea distinta, el número mínimo de desplazamientos necesarios para teclearlo.
Después de cada caso de prueba se escribirá una línea con tres guiones (---).
Entrada de ejemplo
3 6 4 AAAB.D AAAGHI LEEEEK ADKEA B.D ELE AA 1 4 2 ABBC ABC CBA 0 0 0
Salida de ejemplo
4 3 4 0 --- 2 3 ---