Warp-world P13924

Warp-world es un mundo rectangular donde puedes desplazarte caminando (avanzas unas casilla en cualquiera de las cuatro direcciones en un segundo) o usando warp-points: puntos del mundo, representados por una letras, que te permiten teletransporte a cualquier otro punto con la misma letra en tan solo un segundo. Por ejemplo, en el siguiente warp-world

para desplazarte del punto 1 al punto 2 puedes caminar (9 segundos: 8 pasos horizontales y uno vertical) o bien avanzar dos pasos al norte (ignorando el warp-point C), teletransportarte a la casilla A de la primera fila, avanzar un paso al sur y uno al este, teletransporte a la casilla B de la última fila, y avanzar un paso al norte, para un total de 2+1+2+1+1=7 segundos. Observa que el warp-point A tiene 3 puntos de entrada, y que el warp-point D es completamente inútil.

Se te pide que, dado un cierto warp-world, respondas cuál es el mínimo número de segundos necesarios para desplazarte entre varios pares de puntos 1 y 2, como en el ejemplo anterior.

Entrada

Cada entrada empieza con la descripción de un único warp-world: el número F de filas y C columnas del warp-world en una línea, seguido de F líneas de C caracteres cada una, describiendo un warp-world con no más de 26 tipos de warp-points A-Z (el número de warp-points en la entrada es arbitrario). A continuación k preguntas, cada una de las cuales ocupa una línea y consiste de las coordenadas (fila y columna, empezando por 1) del punto 1 y del punto 2, separadas entre si por dos espacios.

Salida

Para cada pregunta, escribe una línea con el mínimo número de segundos necesarios para desplazarte del punto 1 al punto 2 del warp-world.

Puntuación

• TestA:  ‍ Entradas con F,C≤ 50 y k<10 preguntas.  ‍25 Puntos ‍

• TestB:  ‍ Entradas con F,C≤ 100 y k<100 preguntas.  ‍25 Puntos ‍

• TestC:  ‍ Entradas con F,C≤ 200 y k<1000 preguntas.  ‍25 Puntos ‍

• TestD:  ‍ Entradas con F,C≤ 400 y k<10000 preguntas.  ‍25 Puntos ‍