Warp-world P13924


Statement
 

pdf   zip

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

D.....A..
..A....B.
.........
........A
2.....C.C
B.......1

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=72+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 FF de filas y CC columnas del warp-world en una línea, seguido de FF líneas de CC 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 kk 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≤50F,C\le 50 y k<10k<10 preguntas.

  • TestB:   Entradas con F,C≤100F,C\le 100 y k<100k<100 preguntas.

  • TestC:   Entradas con F,C≤200F,C\le 200 y k<1000k<1000 preguntas.

  • TestD:   Entradas con F,C≤400F,C\le 400 y k<10000k<10000 preguntas.

Public test cases

  • Input

    1 25
..A...A..B.....B.C....C..
1 1  1 25
1 25  1 1
1 4  1 25
1 8  1 25

    Output

    12
12
11
8

  • Input

    6 11
C.A..A....B
.A.BA....B.
..BA....B..
.BA....B..A
B.....B..A.
.....B..A.C
1 1  6 11
3 3  6 1
3 3  5 11
6 3  6 3
6 3  5 4
6 10  1 10

    Output

    1
2
3
0
2
5

  • Input

    6 9
D.....A..
..A....B.
.........
........A
......C.C
B........
6 9  5 1
5 1  5 9
5 3  5 9

    Output

    7
6
5
    • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++